Forskningen om datorinlärning, datorns förmåga att inhämta ny kunskap, har gjort stora framsteg på senare år och fått många tillämpningar, men det finns andra viktiga aspekter av AI, till exempel förmågan att lösa problem. Den typ av problem som är ämnet för denna artikel kallas kombinatoriska optimeringsproblem. De kan uppstå inom många tillämpningsområden såsom schemaläggning, planering, design, medicin, robotik, logistik med mera. Gemensamt för den här typen av optimeringsproblem är att de innehåller diskreta val, vilket innebär att de bara kan anta vissa värden till exempel i vilken ordning två lektioner ska schemaläggas, i vilka salar de ska hållas eller hur en cancerpatients strålningsterapi ska schemaläggas. Den andra komponenten i sådana problem är kombinatoriken – vissa kombinationer av diskreta val är tillåtna, andra är otillåtna.
Inte enkelt att skräddarsy en cykel
Produktkonfigurering är ett typiskt kombinatoriskt optimeringsproblem. Säg att du vill köpa en mountainbike av ett visst märke. Du kommer att behöva bestämma en mängd parametrar för just din cykel: hardtail eller heldämpad, ramstorlek, hjulstorlek, framväxel eller singelklinga, färg, och så vidare. Vissa kombinationer kanske inte finns, till exempel en XL ram med 26 tums hjul. Och varje val påverkar givetvis prislappen.
Produktkonfigurering kan vara interaktiv eller automatisk. I interaktiv konfigurering används ett webbgränssnitt som visar alla hittills gjorda val, vilka val som är kvar att göra (och deras valbara alternativ), samt i vilket intervall som priset kommer att landa. I varje interaktion gör du ett nytt val, eller ångrar ett tidigare val, varefter skärmen uppdateras. Så håller man på tills det inte finns några val kvar att göra. I automatisk konfigurering ställs krav upp som ska uppfyllas, samt en målfunktion att optimera. Målet är kanske att hitta en konfiguration med lägsta pris, längsta livslängd, eller något annat. Därefter får verktygen söka efter den konfiguration som optimerar målfunktionen, utan interaktion.
En cykeltillverkare kan ha nytta av ett konfigureringsverktyg för att offerera ”skräddarsydda” produkter till kunder. En kund kan ha nytta av samma verktyg för att snabbt och översiktligt ha koll på alla val och på priset för att ”skräddarsy” sin drömcykel.
Många val bakom varje basstation
För ett företag som Ericsson är stöd för produktkonfiguration helt centralt när produkter ska offereras och säljas. En basstation för mobiltelefoni är en sammansatt produkt som består av hårdvaruenheter: radiosändare och -mottagare, antenner, beräkningsresurser, multiplexers, kablar, med mera. En basstation ska uppfylla en hel rad krav som sändareffekt, antalet mobila enheter som ska kunna anslutas, frekvensband, radioaccessteknologier (3G, 4G, 5G etc.), med mera. Det finns också en stor mängd interna protokoll och begränsningar på vad som får kopplas till vad, och hur. Produktfloran av hårdvaruenheter är naturligtvis omfattande – varje modell har sina specifika förmågor. Rymden av fungerande kombinationer blir helt enkelt orimligt stor för den enskilde säljaren eller ingenjören att hålla reda på. Ericsson har en lång tradition av interaktiv konfigurering av basstationer, med fler och fler inslag av automatisk konfigurering. För att utveckla nya sätt angripa detta kombinatoriska optimeringsproblem har Ericsson tillsammans med RISE tittat på att använda villkorsprogrammering med hjälp av AI, så kallad constraint programming (CP).
Inte ett program men en modell
I CP skrivs, trots namnet, inte ett program som säger hur problemet ska lösas, utan en modell som beskriver lösningarnas egenskaper och (vanligen) målfunktionen. Konkret består modellen av flera delar: problemvariabler, en för varje val att göra; hjälpvariabler; en värdedomän för varje variabel; en målfunktion av några av variablerna; samt villkor som kopplar ihop variablerna genom att ange tillåtna värdekombinationer.
Programvara för CP kallas lösare och består vanligen av ett klassbibliotek för ett programspråk till exempel Java eller C++. Genom att koda en modell med hjälp av det applikationsprogrammeringsgränssnitt (API) som klassbiblioteket definierar, anropas sedan en metod som söker efter den lösning som optimerar målfunktionen, eller den bästa möjliga inom en given tidsbudget. Det finns många varianter av detta paradigm tillexempel se bättre och bättre lösningar allt eftersom de hittas, styra sökningen, och så vidare. Det finns ett stort utbud av lösare, såväl kommersiella som akademiska och open source.
Nackdelen med att koda en modell för en given lösare i ett givet programspråk är att den inte blir portabel till andra lösare.
Portabla modeller tar över
Nackdelen med att koda en modell för en given lösare i ett givet programspråk är att den inte blir portabel till andra lösare. Även om alla lösare i princip har samma funktionalitet kan syntax och uppsättning primitiver skilja sig åt väsentligt, det samma gäller prestanda.
Ett genombrott kom runt 2010 då forskare vid Monash University i Melbourne publicerade ett lösaroberoende språk för CP-modeller, MiniZinc. Forskarna utvecklade också FlatZinc, ett digitalt filformat för lågnivårepresentation av modeller som är läsbart av alla lösare, samt en kompilator från MiniZinc till FlatZinc. Det innebär att modellen i MiniZinc kodas och låter därefter kompilatorn kompilera (översätta) den för den önskade lösaren varefter lösaren räknar fram lösningen eller lösningarna. MiniZinc-teknologin vann snabbt acceptans bland forskare och det faktum att modellerna nu var portabla och lösaroberoende innebar givetvis en stor fördel även för den kommersiella användningen.
Det är de här fördelarna som lett till att Ericsson valt att basera sina automatiska konfigureringsverktyg på MiniZinc. AI-metoden innebär en optimerad lösning på de kombinatoriska problem som produkter med varierande och omfattande funktionskrav har och underlättar skräddarsydda leveranser.
