SE520367C2 - Metod och anordning för interaktiv konfigurering - Google Patents

Description

40 45 55 60 65 5520 367 2 nödvändighet.

Behovet av konfiguration uppstår på olika nivåer. Naturligtvis krävs kon- figurationslösningar på produktionssidan, d.v.s. vid produktkonstruktion, men efterfrågan ökar även på konsumtionssidan. Konsumenterna kräver i allt större utsträckning produkter som är skräddarsydda efter deras specifika behov och smak. Med avseende på särskilda produktsegment (såsom PC- system, bilar och många andra segment) finns det alltså en efterfrågan på datorbaserade system för konfigurationshantering, som kan skötas av en försäljare eller kunden själv (t.ex. en konsument som ska beställa en kon- figurerbar produkt via Internet).

Det finns idag fiera kommersiellt tillgängliga konfigurationshanteringssys- tem för såväl produktkonstruktion som konsumtion. Dessa är baserade på oli- ka kärnteknologier, såsom omfattande databassökning, programmering av ex- plicita begränsningar (constraint programming), satslogiska SAT-algoritmer o.s.v. Ur användarperspektiv är det stor skillnad på ett system där man först gör en serie val och endast i efterhand får reda på om valen överensstämmer med en giltig konfiguration eller ej, och ett system som bara presenterar de alternativ som tillsammans med redan gjorda val utgör del av en giltig konfiguration. Föreliggande uppfinning är integrerad i ett system av det an- dra slaget som använder sig av en boolesk SAT-algoritm och den hänför sig till ett specifikt problem som kan uppstå under konfigurationsprocessen med systemet i fråga. I något skede av konfiguratíonsprocessen kan det hända att användaren upptäcker att vissa val hon önskar göra inte är möjliga på grund av redan gjorda val. I en sådan situation finns det inte någon giltig konfiguration som inbegriper det val som användaren önskar göra samt alla tidigare gjorda val. I det här läget är det önskvärt att användaren erbjuds valmöjligheter som är sådana att hon faktiskt kan göra aktuellt val samtidigt som hon behåller en delmängd av tidigare gjorda val, som är förenlig med det aktuella valet och som skapats med utgångspunkt från hennes önskemål.

Redogörelse för uppfinningen Föreliggande uppfinning löser ett specifikt problem som uppstår i interak- tiva konfigurationssystem av en viss sort. Programmet implementeras också som en del av ett specifikt system av detta slag. Konfiguratorer av den- na typ erbjuder användaren valbara moduler omfattande ömsesidigt utes- lutande alternativ, t.ex. i form av menyer som presenterar ömsesidigt utes- 75 85 90 95 100 105 5É2 0 316 7 lutande alternativ för vissa aspekter av den konfigurerbara produkten. I en sådan meny kan det finnas listor över färger på bilar, olika monitorer för PC-system m.m., allt efter vilken produkt som ska konfigureras. Vissa al- ternativ under en särskild meny kan programmet ha markerat som icke tillgängligt, detta på grund av att användaren tidigare gjort val som är oförenliga med aktuellt val. Användaren kan markera högst ett av resterande alternativ som valt, vilket innebär att det ska inkluderas i den slutgiltiga konfigurationen, eller ett / flera av alternativen som bortvalt vilket i sin tur innebär att alternativet/en inte får inkluderas i konfigurationen. Konfigura- torn har en regelbas (bestående av satslogiska formler) som innehåller (1) formler som uttrycker oförenlighets- och beroendeförhållanden m.m. mellan de olika alternativen; (2) formler som uttrycker vad som är en fullständig konfiguration och (3) formler som anger vilka alternativ som är ömsesidigt uteslutande. När användaren markerar ett alternativ som valt, tillfogas den atomära formel som motsvarar alternativet till regelbasen. Om ett alterna- tiv å andra sidan markeras som bortvalt, läggs negationen av motsvarande atomära formel till i regelbasen. Konfiguratorn tillämpar därefter en boolesk SNF-algoritm för att kontrollera huruvida ytterligare alternativ utgör del av en giltig konfiguration tillsammans med de alternativ som redan markerats som valda (valt). Om det för ett särskilt alternativ inte förhåller sig så, markerar konfiguratorn alternativet som icke tillgängligt.

För att illustrera detta kan vi t.ex. beskriva en konfiguration av ett PC-system med hjälp av den här sortens konfigurator - men som tidigare nämnts kan uppfinningen användas inom många andra områden. För varje valbart alternativ under menyerna _ och även för menyerna själva - finns motsvarande atomära formler. Atomära satslogiska formler är odelbara syn- taktiska enheter som används för att ange att något är fallet. Om användaren exempelvis har markerat menyalternativen hárdvarazprocessor:Pentium III 550Mhz, hårdvarazmonitorzTrinitron 17' ' och programvarazoszLinux som valt, tillfogar konfiguratorn de motsvarande atomära formlerna pIII550, trinitron17 och linux till regelbasen. Icke-atomära formler byggs upp från atomära med hjälp av konnektiver såsom negation (n), konjunktion (A), dis- junktíon (V), materiell ímplikatíon (->) o.s.v. Dessa konnektiver uttrycker sanningsfunktioner (booleska funktioner). Exempelvis har formeln -wwindows värdet sann om och endast om formeln windows har värdet falsk; formeln (pIII550 A trinitronl7) har värdet sann om och endast om både pIII550 110 115 120 125 130 135 140 5l2 0 .. 3.6 7 4"/ och trinitron17 har värdet sann; formeln (pIII550 V trinitron17) har värdet sann om och endast om minst en av formlerna pIII550 och trinitron17 har värdet sann; och slutligen har formeln (pIII550 -> trinitron17) värdet sann om och endast om pIII550 har värdet falsk eller trinitronl? har värdet sann.

Om användaren har markerat ett menyalternativ som bortvalt, till- fogas negationen av motsvarande formel till regelbasen. Om användaren exempelvis har markerat menyalternativet hàrdvarazhárddisk: 1 ,4GB som bortvalt, läggs formeln -hd1.4 till i regelbasen.

Utöver de formler som resulterar från användarvalen, innehåller regel- basen som vi tidigare nämnt: (1) formler som uttrycker beroende- och oförenlighetsförhållanden mellan de valbara alternativen, som t.ex. formlerna ((linux/\pIII550) -> -zip) som anger att ett datorsystem med Pentium III 550 MHz CPU som kör opera- tivsystemet Linux inte kan utrustas med en zip-drive, och (fievmsoffice) -> (windows V macos)) som anger att programmen Internet Explorer och Mi- crosoft Oflice kräver något av operativsystemen Microsoft Windows eller Ma- cOS; (2) formler som uttrycker vad som är en fullständig konfiguration, i det- ta fall ett fullständigt datorsystem, Detta görs med hjälp av en formel av följande slag: (processor/\minne/\hårddiskAtangentbordA. . ./\os), där de olika konjunkterna (processor, minne, hårddisk, tangentbord, . . . ,os) definieras av formler såsom (processor -+ (pII350 V pII400 V pIII400 V ...V pIII850)), (minne -> (32MB V 64MB V 128 MB V.. .V l024MB)), o.s.v. Slutligen; (3) formler som anger vilka alternativ som är ömsesidigt uteslutande såsom (pII350 -> (flpII400 /\ -\pIII400 /\ . . . /\ -fipIII85Û)) /\ (pII400 -> ( Formler av det andra slaget krävs för att undvika situationer där användaren har gjort ett antal val som är förenliga med varandra men som ändå inte utgör del av en fullständig konfiguration, d.v.s. det fullständiga systemet kräver en viss del som inte är förenlig med användarens val. SAT-problemet med avseende på en mängd satslogiska formler är att avgöra huruvida samtliga formler i mängden i fråga samtidigt kan vara sanna eller ej, d.v.s. huruvida de tillsammans är satisfierbara. Om vi antar att mängden i fråga innehåller adekvata och tillräckligt starka formler av typen (1-3) ovan, i kombination 145 150 155 160 165 170 175 520 367 med formlerna som representerar användarvalen, innebär fastställandet av huruvida formlerna i denna mängd tillsammans är satisfierbara väsentligen samma sak som att fastställa huruvida användarvalen ingår i en giltig kon- figuration, d.v.s. i en möjlig (och tillgänglig) kombination av delar som till- sammans utgör en helhet av slaget i fråga. En SAT-algoritm accepterar som input en formelmängd av nämnda slag och avgör huruvida de atomära form- ler som förekommer i inmatade formler kan tilldelas sanningsvärden, så att alla inmatade formler har värdet sann.

Uppfinningen avser specifikt en situation där användaren under en in- teraktiv konfiguration medelst en konfigurator av ovan beskrivna typ, kom- mer till en punkt där hon vill välja ett särskilt alternativ som redan uteslu- tits på grund av hennes tidigare gjorda val, d.v.s. alternativet är markerat som icke tillgängligt. Exempelvis kan en användare som konfigurerar ett PC-system i något skede upptäcka att det inte går att välja alternativet hàrdvarazminnezlO24MB. Anledningen till detta kan vara att användaren precis i början av konfigurationen valt hárdvarazprocessor:Pentium II 25OMI-Iz och det finns inte några moderkort med tillräcklig minnesplats för 1024MB RAM-minne, som är kompatibla med denna typ av processor och därför innehåller konfiguratorns regelbas en begränsning i detta avseende.

Användaren kanske mycket hellre önskar få l024MB RAM-minne än vald typ av processor. Om hon fick veta att hon skulle kunna få 1024MB RAM- minne om hon bara valde en annan processor skulle hon förmodligen gärna göra detta och på så sätt vara mycket mer tillfreds med konfigurationen än annars.

I situationen som beskrivs ovan strider användarens aktuella önskemål (att välja ett visst alternativ) mot hennes tidigare gjorda val. Eftersom det val hon nu önskar göra inte är förenligt med (vissa av) hennes tidigare val måste hon avmarkera minst ett (och förmodligen flera) av dessa tidigare val för att kunna få sin önskan uppfylld. Om hon anser att de tidigare valen är viktigare än det aktuella önskemålet, måste hon självfallet acceptera att hon inte kan välja det. I annat fall skulle hon däremot kanske vilja annullera motstridiga val som är av mindre vikt för henne så att de aktuella önskemålen i stället kan uppfyllas. En metod som erbjuder användaren denna möjlighet skulle tillföra henne verkligt mervärde eftersom hon i en dylik situation med hjälp av pro- grammet skulle kunna konfigurera en produkt som bättre överensstämmer med hennes önskemål än annars. En sådan metod skulle därför vara yt- 180 185 190 195 200 210 5210 367 terst värdefull i processen att uppnå en optimal konfiguration. Föreliggande uppfinning avser en metod som har exakt denna förmåga.

Om användaren alltså insisterar på att göra ett val som inte är förenligt med hennes tidigare val, ombeds hon enligt föreliggande uppfinning att ran- gordna sina tidigare val med avseende på deras relativa betydelse för henne.

Därefter avmarkerar konfiguratorn tidigare gjorda val i följd (dock ligger de fortfarande kvar i minnet). Konfiguratorn börjar med det minst priorit- erade valet och arbetar sig uppåt genom att i varje steg kontrollera huru- vida resterande mängd användarval är förenlig med användarens aktuella önskemål och stannar slutligen när så är fallet. Denna avmarkering är ku- mulatív eller additív i meningen att tidigare avmarkerade alternativ' förblir avmarkerade under processen, och nya avmarkerade val successivt läggs till bland mängden avmarkerade val. På så sätt kommer algoritmen att detek- tera en (lägsta) punkt (i prioritetsordningen), sådan att mängden av de valda (valt) och bortvalda (bortvalt) alternativ som befinner sig ovanför denna punkt, är förenlig med det icke tillgängliga (icke tillgängligt) alternativ som användaren insisterar på att välja. En alternativ, men logiskt ekvivalent metod är att först avmarkera alla tidigare gjorda val och därefter mata in dem från minnet igen i (fallande) prioritetsordning, kumulativt (d.v.s. de adderas successivt till mängden val som matas in på nytt) och därefter för varje på detta sätt prioriterade delmängd av användarens tidigare val, kontrollera hu- ruvida denna är förenlig med det icke tillgängliga (icke tillgängligt) al- ternativet i fråga och terminera vid den sista (och största) förenliga mängden.

Vilken av dessa metoder som bör väljas är en lämplighetsfråga _ båda algoritmerna terminerar på samma ställe i listan. Emellertid kan en av dem vara snabbare än den andra bl.a. beroende på termineringspunktens relativa position. Slutligen hämtar algoritmen samtliga av användarens tidigare mark- erade alternativ från minnet och matar in dem på nytt. Användaren får nu veta att om hon tilldelar det icke tillgängliga (icke tillgängligt) alterna- tivet i fråga högre prioritet än de från mängden uteslutna alternativen enligt denna beräkning, kan hon välja alternativet eftersom det då blir förenligt med den beräknande mängden valda (valt) och bortvalda (bortvalt) alternativ med högre prioritet än de uteslutna.

Om användaren gör denna omprioritering och nu försöker välja icke tillgängligt alternativ i fråga får hon veta att detta är möjligt men att de lägre prioriterade alternativ (och bortvalda alternativ) som hon tidigare 215 220 225 230 235 240 245 I5201 367 ~7 markerat, och som är oförenliga med det nya valet, i så fall kommer att raderas. Om användaren nu väljer icke tillgängligt alternativ i fråga, kommer alternativen med lägre prioritet först att avmarkeras (dvs. inte längre markeras som antingen valt eller bortvalt. Dock kommer informa- tionen om användarens tidigare val som är knutna till dessa parametrar att ligga kvar i minnet. Därefter försöker algoritmen att mata in de tidigare markerade alternativen på nytt, ett och ett i fallande prioritetsordning, för att erhålla en maximal delmängd av tidigare användarval, som är förenlig med regelbasen och tidigare icke tillgängligt alternativ.

En avsevärd fördel med denna metod är att användaren kan välja ett al- ternativ som markerats som icke tillgängligt på grund av tidigare gjor- da val med vilka det inte är förenligt, samtidigt som hon får möjlighet att behålla så många av de tidigare alternativen som möjligt. På så sätt kan användaren erhålla en produkt som överensstämmer med hennes önskemål och som hon kan känna sig mycket nöjdare med - på kortare tid och med lägre arbetsinsats än annars.

Tidigare känd teknik I “7099/13411 beskrivs en tidigare känd teknik som hänför sig till ett prob- lem av samma slag som kan lösas av föreliggande uppfinning. Metoden i fråga är tänkt att integreras i en interaktiv konfigurator av den sort som beskrivs i VVO99/l3413 av samma patentsökande.

När en användare av denna konfigurator vill välja ett valbart alternativ, som på grund av tidigare val redan markerats som icke tillgängligt, kommer systemet att identifiera alla maximala mängder av tidigare användarval som är förenliga med det icke tillgängliga alternativet i fråga samt regelbasen.

En lista över maximala mängder presenteras nu för användaren som ombeds välja en utav dem. En sådan här mängdlista kan naturligtvis vara ganska lång i vissa fall och även svår att överblicka. För att underlätta urvalet får användaren möjlighet att välja ut några av de tidigare valen som måste ingå i de maximala mängder som presenteras för henne. På det här sättet kan antalet alternativ som användaren får reduceras.

Enligt denna tidigare kända metod identifieras maximala mängder av tidigare gjorda val genom att alla alternativa sätt att avmarkera något av de tidigare valen gås igenom och därefter alla alternativa sätt att avmarkera två tidigare val o.s.v. Varje gång kontrolleras huruvida mängden resterande val 250 255 260 265 270 275 280 1520, 367 är förenlig med det icke tillgängliga alternativet i fråga och regelbasen. Om vi låter P = {p1, . . . pk} representera alla (k) tidigare gjorda val, och q represen- tera det icke tillgängliga alternativet som användaren insisterar på att göra, kontrollerar metoden först huruvida någon av mängderna P\{p1}, P\{p2}, . . . P\{pk} är förenlig med q och regelbasen. Därefter går den vidare med att kontrollera om någon av mängderna P\{p1,p2}, P\{p1,p3}, .. .P\{pk_1,pk} är förenlig o.s.v. På så vis identifieras alla maximala mängder av P som är förenliga med regelbasen och q.

En stor nackdel hos denna tidigare kända teknik, jämfört med föreliggande uppfinning, är att antalet satisfierbarhetskontroller är mycket större, vilket resulterar i betydligt mer tidskrävande beräkningar och självfallet nedsatt användarifänlighet. Enligt föreliggande uppfinning krävs endast ett (1) sätt för att annullera ett användarval i P = {p1, . . .pk}, medan det i metoden som beskrivs i WO99/l3411 finns k sätt att beakta vid annullering av ett val. Vidare krävs bara ett (1) sätt för att annullera två val i stället för och vanligtvis bara 1 sätt för att annullera n val i stället för olika sätt.

Följaktligen blir största antalet upprepningar, enligt föreliggande uppfinning, lika stort som antalet tidigare gjorda användarval minus ett (eftersom den tomma mängden Q) inte behöver kontrolleras), medan antalet i den metod som beskrivs i \vo99/1s411 uppgår nu gig, _ 1 = zk _ 2, där k är antalet tidigare gjorda användarval.

Avsedd implementation En lämplig implementation av uppfinningen illustreras med hjälp av ett antal flödesscheman (fig. 1-4) som kommenteras nedan.

I flödesschemana beskrivs algoritmer som företrädesvis implementeras i ett datorprogram. Detta ska kunna köras i en monitoransluten dator som är kopplad till några inmatningsenheter, som t.ex. tangentbord och mus. Med hjälp av detta program kommer ett menysystem i enlighet med beskrivningen ovan att visas på monitorn. Användaren kan med hjälp av inmatningsenheter- na markera ett menyalternativ på monitorn som valt eller bortvalt. Vissa alternativ kan även markeras som tex. icke tillgängligt på grund av pro- gramaktivitet. Även andra inmatnings- och utmatningshändelser utväxlas via dessa inmatnings- och utmatningsenheter mellan användaren och datorn som programmet körs i. Datorn som kör programmet kan vara uppställd på en plats och vara ansluten till monitorn och inmatningsenheterna - direkt 285 290 295 300 305 315 -520- 367. 9 eller indirekt - via en dator som står någon annanstans. Det kan också vara så att delar av nämnda program exekveras i en dator och en annan del i någon annan dator som är ansluten till den första.

För att underlätta följande beskrivning börjar vi med att definiera nâgra termer: Menyalternativen som användaren kan markera som valt eller bortvalt och som programmet i uppfinningen kan markera som icke tillgängligt, kallar vi valbara alternativ. I nämnda avsedda implementation motsvaras var- je valbart alternativ av en variabel som representerar detta. Dessa variabler kallar vi valbara variabler. De valbara variablerna förhåller sig till de valbara alternativen på så sätt att de antar värdet 1 när motsvarande valbara alter- nativ markeras som valt, och 0 när motsvarande valbara alternativ markeras som bortvalt. Vidare motsvaras varje valbar variabel av en atomär satslo- gisk formel som uttrycker värdet för variabeln i fråga. Om p refererar till en valbar variabel använder vi p för att referera till motsvarande atomära formel. Att exempelvis värdet för p är 1 uttrycks med formeln p, och att det är 0 genom negationen -p av formeln p. Om variabeln p å andra sidan inte är definierad - vilket är fallet när motsvarande menyalternativ' inte är mark- erat ~ finns det ingen formel som uttrycker detta. Frånvaron av både formel p och -=p indikerar således att motsvarande variabel p inte är definierad och att motsvarande menyalternativ inte är markerat.

Vi refererar till det valbara alternativet som motsvarar den valbara vari- abeln p med p. I kraft av' dessa motsvarigheter kommer vi för enkelhetens skull i fortsättningen att tala om mängder av valbara variabler som är förenliga eller oförenliga med regelbasen. Vad som alltså menas är naturligtvis att den formelmängd som uttrycker värdet för dessa variabler antingen är förenlig eller oförenlig med regelbasen.

I den avsedd implementationen av uppfinningen kommer programmet efter varje användarinmatning, dvs. efter det att användaren markerat ett menyalternativ som antingen valt eller bortvalt, att gå igenom de menyal- ternativ som användaren ännu inte markerat. För vart och ett av alternativen q läggs motsvarande formel q till i formelmängden som motsvarar mängden pl . . .pk av valbara variabler som representerar tidigare användarval. Mängden kommer sedan tillsammans med en mängd formler som uttrycker olika be- gränsningar för de valbara alternativen (regelbasen) att sändas till en imple- mentation av en SAT-algoritm för att fastställa om mängden är konsistent.

Om så inte är fallet kommer menyalternativet (q som motsvaras av variabeln 320 325 335 340 345 350 355 520" 367 /0 q att markeras som icke tillgängligt. Om mängden å andra sidan är kon- sistent, kommer nästa omarkerade alternativ att kontrolleras på samma sätt.

Vi kallar ett alternativ som markerats som icke tillgängligt helt enkelt för icke tillgängligt menyalternativ och talar generellt om tillgängligheten för ett sådant menyalternativ och avser då huruvida det är tillgängligt eller ej, allteftersom det faller sig. Mängden pl . . . pk av tidigare användarval tillde- las en förinställd (default) prioritetsordning, som exempelvis är baserad på i vilken ordning som användaren markerat alternativen i fråga, eller på någon användarprofil som hänför sig till den specifike användaren, eller på någon annan princip.

Flödesschemat i figur 1 beskriver följande tänkbara implementation i en- lighet med uppfinningen: Algoritmen aktiveras när en användare önskar välja ett valbart alternativ F; som är markerat som icke tillgängligt på grund av tidigare gjorda användarval som representeras av de valbara variablerna pl . . pk. Till att börja med tilldelas variablerna en förinställd (default) prior- itetsordning i vilken pl har högsta och pk lägsta prioritet. För 1 g n, m g k om m < n så antas pm ha högre prioritet än pm d.v.s. det finns inga alter- nativ som har samma prioritetsgrad. Först får användaren frågan om hon vill rangordna sina tidigare val med utgångspunkt från hur viktiga de är för henne, m.a.o. göra en omprioritering. Om hon svarar Nej kommer algoritmen att tillämpa den för-definierade prioritetsordningen och direkt kalla subrutin S2 (fig. 3) som identifierar en mängd P valbara variabler som representer- ar tidigare val som är förenliga med q och regelbasen. Denna delmängd av {p1 . . .pk} är maximal och prioriterad på ett sätt som kommer att redogöras för nedan (fig. 3). Om användaren i stället svarar Ja går algoritmen först in i subrutin S1 (fig. 2), som gör det möjligt för henne att omprioritera sina tidigare val pl . . pk, för att därefter gå vidare till subrutin S2. Eftersom P U {q} är förenlig med regelbasen är valet (i förenligt med användarens önskemål. Detta förutsatt att q tilldelas en prioritetsgrad som är minst lika hög som för något av alternativen i P, eller m.a.o. högre än för samtliga alternativ i {p1 . . .pk}\P (se förklaring till lig. 3). Användaren får nu därför frågan om (1 har högre prioritet för henne än alla de alternativ som motsvarar {p1 _ . .pk}\P. Om användaren svarar Nej avslutas algoritmen då valet av al- ternativet G1 (som motsvarar variabel q) uppenbarligen inte är förenligt med användarens önskemål, vilket hon också informeras om. Om användaren å andra sidan svarar Ja går algoritmen in i subrutin S3 (fig. 4) som identifierar 360 365 370 375 380 385 390 = s2o 567 ll en mängd Q så att P Q Q C_l {pl . . .pk}, Q U {q} är förenlig med regelbasen, och Q är maximal på ett sätt som vi kommer att redogöra för nedan (fig. 4).

Flödesschemat i fig. 2 beskriver subrutin S1 av algoritmen som återges i fig. 1. Subrutinen börjar med en mängd pl. . .pk av valbara variabler som representerar tidigare användarval rangordnade i fallande prioritetsordning enligt ovan (fig. 1). Först ombeds användaren att välja ut ett alternativ från listan pl . . .pk för att omprioritera det, d.v.s. ett alternativ som hon vill tilldela en annan, relativ prioritet i förhållande till övriga alternativ i lis- tan. Användaren väljer ett sådant alternativ pm (vi kallar denna variabel s).

Resterande variabler pl . . . pm_l, pmil . . .pk behåller sina respektive platser i ordningen. Vi kommer hädanefter att kalla dem pl . . .pk_l (för m < n § k, får pk nu benämningen p,,_l).

Användaren ombeds i detta skede att välja en ny prioritetsgrad (ett av för det valda alternativet s, varpå hon väljer ny prioritetsgrad n 6 {1 . . . Därefter ordnar algoritmen variablerna pl . _ .pk_l och s på följande sätt: Förj < n behåller respektive pj sin plats i listan; s tilldelas position n och för n í j < k, tilldelas pJ- position j + 1.

Användaren får nu frågan om hon är nöjd med den nya prioritetsordnin- gen pl . . .pk för variablerna eller om hon vill göra ytterligare omprioriteringar.

Om användaren väljer Ja går algoritmen in i subrutinen igen. Väljer hon i stället Nej går algoritmen ut ur denna subrutin. Subrutinen producerar återigen en lista över användarval pl . . .pk som nu är rangordnade utifrån användarens önskemål. Subrutinen kan självfallet implementeras av stan- dardrutiner för manipulation av ordnade datastrukturer.

Flödesschemat i fig. 3 beskriver subrutin S2 av algoritmen som återges i fig. 1. Precis som subrutin S1 börjar subrutinen med en mängd {pl . . .pk} variabler som representerar tidigare användarval, rangordnade i fallande pri- oritetsordning och en variabel q som representerar något icke tillgängligt valbart alternativ som användaren insisterar på att välja. Först initialiserar subrutinen en räknare l till platsen för sista alternativet i mängden {pl . _ .pk}, d.v.s. l tilldelas värdet k. Därefter tillfogas atomära formler och negationer av atomära formler som motsvarar variablerna pl . . .pl_l och q = 1 till regel- basen (q och för 1 g m 3 l - 1 antingen pm eller ppm beroende på om värdet för pm är l eller O), och en SAT-algoritm anropas för att kontrollera huruvida denna formelmängd är satisfierbar. Om den inte är det kontrollerar subrutinen först om mängden {pl . . .pl_l} är tom ({pl . . .pll} är den tomma 395 400 405 410 415 420 425 52 0. . 3.67 /-'¿ mängden (Û). I så fall är q inte förenlig med regelbasen vilket innebär att det inte går att välja det valbara alternativet q om inte regelbasen ändras. Därför terminerar algoritmen i detta fall. Om å andra sidan mängden (pl . . . p¿_1} inte är tom, tas 1 bort från räknaren l och subrutinen fortsätter att kon- trollera delmängden {p1 . . .p,_2} av {p1 . . .pk} på samma sätt.

Vid varje upprepning tar subrutinen på detta vis bort det lägst prioriter- ade alternativet varför borttagandet i detta avseende blir (omvänt) successivt.

Borttagandet är även kumulativt i den bemärkelsen att borttagna alternativ förblir borttagna och nya borttagna alternativ vid varje upprepning tillfogas till mängden tidigare borttagna alternativ.

Om q är förenlig med regelbasen kommer det för något l > O då att finnas en delmängd (pl . . .p¿_1} av {p1 . . .pk} som är förenlig med q och regelbasen.

Subrutinen kommer att hitta en delmängd P som är beskaffad på så sätt att varje element i P (om något sådant finnes) har högre prioritet än samtliga element i {p1...pk}\P. Sålunda är denna delmängd ett initialsegment av {p1.. .pk}. Mängden P är i detta avseende prioriterad. P = {p1. . .p¿_1} är även maximal i det avseendet att om l' > l så är {p1...p¿f_1} inte förenlig med q och regelbasen. På så sätt är P det maximala initialsegmentet av {p1 ...pk}, som är förenligt med q och regelbasen. När mängden P identi- fierats på detta sätt, avslutas subrutinen med att q, {p1...pk} returneras och l indikerar det element p, i {p1...pk} som har högsta prioritet utanför mängden P.

Flödesschemat i fig. 4 beskriver subrutin S3 för algoritmen som återges i fig. 1. Subrutin S3 börjar med parametrarna q, (111 . . .pk} och l som överförts från subrutin S2 och som representerar icke tillgängligt valbart alter- nativ q som användaren önskar välja samt den maximala och prioriterade (på det sätt som beskrivs i figur-förklaringen ovan) delmängden P som är förenlig med q och regelbasen. Subrutinen har till uppgift att identifiera en maximal delmängd R av {p1...pk}\P så att Q = R U P blir förenlig med q och regelbasen och genereras med hänsyn tagen till den relativa prioritet som användaren tilldelar elementen i mängden {p1 . . .p,,}\P enligt följande: Låt RB vara regelbasen. Vi säger att en delmängd S av (191 . . .pk} är maxi'- malt q-konsistent (med avseende på RB) om S U {q} U RB är en maximalt konsistent mängd i förhållande till {p1...pk}, d.v.s. om S U {q} U RB är konsistent och om r E {p1 . . .pk}\S så är SU {r} U {q} U RB inte konsistent.

Q är uppenbarligen en maximalt q-konsistent extension (superset) av P i 430 435 440 445 450 520 367 /3 detta avseende. Om Q' är någon annan maximalt q-konsistent extension av p innebär det att något element i r i Q\Q' har högre prioritet än samtliga element i Q'\Q. Således genereras Q på ett sätt som battre överensstämmer med användarens önskemål än samtliga alternativa maximalt q-konsistenta mängder.

Först initialiseras en räknarvariabel n tilll. Därefter tillfogas formelmängden som motsvarar variablerna {p1 _ . _ p,,} och formeln q till regelbasen och därefter skickas formelmängden till SAT-algoritmen. Om formelmängden inte är satis- fierbar (vilket förstås är fallet om n = l), kommer värdet för variabeln p” att ställas in på odefinierad vilket motsvarar en avmarkering av motsvarande valbara alternativ. Om formelmängden å andra sidan är satisfierbar förblir värdet för p” oförändrat. Därefter kontrolleras huruvida n < k och om så inte är fallet avslutas subrutinen. Annars ökar räknaren n stegvis och subru- tinen påbörjar en ny upprepning. Om {p1 . . .p,,} nu innehåller odefinierade variabler måste vi ha klart för oss att inga formler som motsvarar dessa variabler räknas med bland de formler som motsvarar variablerna i denna mängd, eftersom det i så fall ~ som vi tidigare poängterade ~ inte finns några motsvarande formler.

Subrutinen fungerar således på ett .successivt sätt i den bemärkelsen att den går igenom listan med alternativ p¿ . . .pk i ordningsföljd. Dessutom är den kumulatív eller addítw i det att de alternativ som under tidigare up- prepningar tillförts den mängd vars förenlighet skall kontrolleras, ligger kvar trots att nya alternativ tillkommer.

Claims (3)

520" 367 f? Patentkrav

1. Metod för interaktiv konfiguration i ett interaktivt konfigurationssys- tem med hjälp av vilket en användare kan konfigurera en konfigurerbar produkt genom att successivt välja, d.v.s. inkludera olika valmöjligheter (alternativ) som representerar olika produktdelar i konfigurationen, sådan att åtkomligheten för ytterligare valmöjligheter fastställs med hjälp av en algoritm som inbegriper en boolesk SAT-algoritm som avgör satisfierbarheten hos formler, inklusive satslogiska sådana, som repre- senterar användarvalen och ovan nämnda ytterligare valmöjligheter till- sammans med en regelbas bestående av formler som uttrycker oförenlig- hets- och beroendeförhållanden kännetecknad av att en användare som önskar välja ett på grund av tidigare användarval icke tillgängligt al- ternativ, får möjlighet att annullera ett minimalt antal tidigare val för att på så sätt kunna behålla en maximal delmängd av tidigare val, som är förenlig med regelbasen och det icke tillgängliga alternativet. An- nulleringen utförs i enlighet med användarens relativa preferenser med avseende på tidigare gjorda val genom att följande steg utförs: a) tidigare användarval tilldelas en prioritetsordning, därefter b) fastställs en maximal delmängd av tidigare användarval med högre prioritet än samtliga de val som inte ingår i nämnda delmängd, sådan att denna delmängd är förenlig med regelbasen och nämnda icke tillgängliga alternativ; och slutligen, c) om användaren tilldelar nämnda icke tillgängliga alternativ högre prioritet än alla tidigare val som uteslutits från nämnda delmängd så genereras en extension av nämnda delmängd av användarval, som är en maximal delmängd av användarval, som är förenlig med regelbasen och nämnda icke tillgängliga alternativ, skapad med utgångspunkt från användarens önskemål.

2. Metod enligt patentkrav 1, kännetecknad av att åtkomsten till ytterli- gare alternativ fastställs efter varje användarinmatning av nämnda slag.

3. Metod enligt patentkrav 1, kännetecknad av att användaren även kan bortvälja, d.v.s. utesluta, olika alternativ som representerar produkt- delar från konfigurationen. 35 40 45 55 60 10. 11. 520 367 IS' . Metod enligt patentkrav 1 kännetecknad av att regelbasen innehåller formler som uttrycker krav på fullständighet. Metod enligt patentkrav 1 kännetecknad av att den delmängd som fastställts i steg (b) uppnås genom att successivt och kumulativt an- nullera nämnda tidigare gjorda val, i stigande prioritetsordning samt att vid varje upprepning kontrollera med nämnda algoritm huruvi- da mängden resterande användarval är förenlig med regelbasen och nämnda icke tillgängliga alternativ. Metod enligt patentkrav 1 kännetecknad av att den delmängd som fastställs i steg (b) uppnås genom att successivt och kumulativt ska- pa en delmängd av nämnda tidigare val, i fallande prioritetsordning och att vid varje upprepning kontrollera med nämnda algoritm huru- vida denna delmängd av användarval är förenlig med regelbasen och nämnda icke tillgängliga alternativ. . Metod enligt patentkrav 1 kännetecknar! av att den delmängd som skapas i steg (c) uppnås genom att successivt och kumulativt, i fal- lande prioritetsordning lägga till nämnda uteslutna alternativ till den delmängd som fastställs i steg (b), och vid varje upprepning kontrollera med nämnda algoritm huruvida extensionen av nämnda delmängd som skapats på detta sätt är förenlig med regelbasen och nämnda icke tillgängliga alternativ, och om så är fallet, behålla det uteslutna al- ternativet, och om så inte är fallet utesluta det. . Metod enligt patentkrav 1, kännetecknaa' av att prioritetsordningen som tilldelas tidigare användarval i steg (a) utförs av användaren själv. . Metod enligt patentkrav 1, kännetecknad av att tidigare användarval i steg (a) tilldelas en förinställd (default) prioritetsordning. Metod enligt patentkrav 9, kánnetecknad av av att användaren i efter- hand kan modifiera den förinställda prioritetsordningen. Metod enligt patentkrav 9, kännetecknar! av att förinställd prioritet- sordning fastställs med utgångspunkt från i vilken ordning användaren gjort sina tidigare val. 70 75 80 90 95 100 12. 13. 520 367 /6 Metod enligt patentkrav 9, kännetecknar! av att den förinställda pri- oritetsordningen fastställs utifrån en användarprofil som hänför sig till användaren i fråga. Anordning som inbegriper en terminal med monitor och inmatningsen- heter, anslutna till en dator i vilken körs ett program som via monitorn presenterar ett menysystem för användaren så att denna med hjälp av inmatningsenheterna kan utföra en interaktiv konfiguration av en produkt genom att successivt välja, d.v.s. i konfigurationen inkludera olika menyalternativ som representerar produktdelar och där program- met implementerar en metod som efter varje användarinmatning gör att åtkomligheten för ytterligare menyalternativ fastställs med hjälp av en algoritm som inbegriper en boolesk SAT-algoritm som avgör satis- fierbarheten för formlerna ~ inklusive satslogiska sådana w som rep- resenterar användarens val samt ytterligare menyalternativ, tillsam- mans med en rcgelbas med formler som uttrycker oförenlighets- och beroendeförhållanden samt där åtkomsten till ytterligare menyalter- nativ presenteras för användaren via monitorn kännetecknad av att en användare som önskar välja ett på grund av tidigare användarval icke tillgängligt alternativ får möjlighet att annullera ett minimalt an- tal tidigare användarval för att på så sätt kunna behålla en maximal delmängd av tidigare val, som är förenlig med regelbasen och nämnda icke tillgängliga alternativ. Annulleringen görs utifrån användarens rel- ativa preferenser med avseende på tidigare gjorda val genom att följande steg utförs: a) tidigare användarval tilldelas en priorítetsordning, därefter b) fastställs en maximal delmängd av tidigare användarval med högre prioritet än samtliga av de val som inte ingår i nämnda delmängd, sådan att denna delmängd är förenlig med regelbasen och nämnda icke tillgängliga alternativ; och slutligen, c) om användaren tilldelar nämnda icke tillgängliga alternativ högre prioritet än alla tidigare val som uteslutits från nämnda delmängd så genereras en extension av nämnda delmängd av användarval som är en maximal delmängd av användarval som är förenlig med regelbasen och nämnda icke tillgängliga alternativ, skapad i en- lighet med användarens önskemål.