Constraint Satisfaction Problemen Oplossen met Java

Heb je ooit geprobeerd een vergadering te plannen voor een groep personen met drukke agenda’s, een kruiswoord- of Sudoku-puzzel geprobeerd op te lossen, of geprobeerd om schaarse resources te koppelen aan activiteiten? Zo ja, dan heb je, bewust of onbewust, te maken gehad met een Constraint Satisfaction Probleem (CSP). Deze problemen vergen een bepaalde mate van intelligentie om adequaat opgelost te kunnen worden, en kunnen niet automatisch opgelost worden middels reguliere algoritmes binnen een acceptabele tijd. Dit artikel presenteert een efficiënte manier om dergelijke problemen op te lossen en geeft aan hoe dit in Java geïmplementeerd kan worden.

Constraint Satisfaction Problemen – Een Voorbeeld

Commerciële Haven
Op een commerciële haven moeten roosters gemaakt worden voor het laden en lossen van 10 schepen, waarbij slechts 5 aanlegplaatsen gebruikt kunnen worden. Hierbij bestaan veel criteria (constraints) voor het selecteren van de juiste aanlegplaats voor een specifiek schip. Sommige aanlegplaatsen zijn bijvoorbeeld te klein voor bepaalde schepen, sommige schepen moeten eerder dan andere schepen gelost worden, sommige aanlegplaatsen zijn duurder in gebruik dan andere, de lading van bepaalde schepen bevindt zich dichterbij bepaalde aanlegplaatsen dan andere, etcetera.

Een mogelijkheid om een goed of optimaal rooster te vinden is ‘generate and test’: genereer alle mogelijke permutaties van schepen en aanlegplaatsen, selecteer hieruit de oplossingen die geldig zijn, bepaal de bijbehorende kosten van elke geselecteerde oplossing, en selecteer tot slot de beste (e.g., goedkoopste) oplossing. Binnen dit voorbeeld betekent dit dat 5¹⁰ (ongeveer 10.000.000) alternatieven geëvalueerd moeten worden indien de genoemde brute force aanpak gebruikt wordt. Indien de computer die gebruikt wordt om dit probleem op te lossen bijvoorbeeld een alternatief per milliseconde kan evalueren, dan zal het probleem binnen ongeveer 3 uur opgelost worden.

Business Is Booming – En De Technologie?

Stel nu, 10 jaar later, dat de zaken goed gaan, en de situatie zich ontwikkeld heeft tot 20 schepen en 10 aanlegplaatsen. Het vinden van een optimaal rooster betekent nu dat 10²⁰ alternatieven geëvalueerd moeten worden, wat resulteert in een rekentijd van ongeveer 3.000.000.000 jaar.

Uiteraard kan een 10 keer krachtigere processor aangeschaft worden, waardoor de rekentijd gereduceerd wordt tot een redelijkere 300.000.000 jaar ;-) De duidelijke conclusie is dat dergelijke brute force algoritmes niet werken voor dit type problemen. Het transformeren van het genoemde brute force algoritme naar bijvoorbeeld een uitgebreider backtracking algoritme zal de situatie ietwat verbeteren, maar niet significant.

Een andere, wellicht aantrekkelijke doch naïeve strategie omvat het verdelen van de haven in twee segmenten, en ieder segment apart te roosteren. Dit zal resulteren in een rekentijd van ongeveer 6 uur (twee maal de eerdergenoemde 3 uur), wat de enorme impact van het aantal variabelen op dit type problemen schetst. Echter, feit is dat de oplossingen binnen deze aanpak verre van optimaal zullen zijn en, nog erger, men weet niet hoe ver van optimaal, en hoeveel geld dus verkwist wordt. Men kan net zo goed het 3.000.000.000-jaar-programma voor 6 uur laten draaien, en de goedkoopste oplossing uit de gegenereerde solution space selecteren. Het resultaat zal hoogst waarschijnlijk van dezelfde (lage) kwaliteit zijn.

Constraint Satisfaction Problemen – Overzicht

Algemeen
Constraint Satisfaction Problems (CSPs) zijn complexe zoekproblemen die gedefinieerd worden in termen van variabelen, diens domeinen en constraints (beperkingen / randvoorwaarden) op deze variabelen. Real-word voorbeelden van CSP’s bevinden zich op het vlak van bio-informatica (DNA-sequence analyse), geavanceerde plannings- en roosteringsproblemen, resource allocation problemen, logistiek, natuurlijke taalverwerking, circuit-ontwerp en puzzels zoals Sudoku, Go, kruiswoordpuzzels, schaken, dammen, Mastermind en Scrabble.

Vanuit een complexiteitsoogpunt zijn al deze problemen grotendeels gelijk. Wat ze met elkaar gemeen hebben is het feit dat ze enorm grote search spaces (zoekruimtes) hebben, die combinatorisch groeien naarmate het aantal variabelen toeneemt – deze karakteristieke eigenschap van CSP’s wordt ‘combinatorial explosion’ genoemd. Deze problemen zijn zogenaamde NP-complete problemen, en kunnen in het algemeen niet binnen een acceptabele tijd opgelost worden met traditionele (e.g., brute force) algoritmes, ook niet met krachtige processoren.

Formele Definitie

Een Constraint Satisfaction Probleem bestaat uit een verzameling variabelen X = {x1,...,xn}, voor elke variabele xi een domein Di dat de mogelijke waarden voor die variabele bevat, alsmede een verzameling constraints Ci tussen variabelen die beperkingen oplegt aan de waarden die de variabelen kunnen aannemen.

Op basis hiervan kan bijvoorbeeld het volgende eenvoudige CSP gedefinieerd worden: variabelen V = {X, Y, Z}, domeinen DX = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, DY = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, DZ = {0, 1, 2, 3, 4, 5, 6,7, 8,9, 10}, constraints C1 = [X == 4], C2 = [X < Y], C3 = [Y > Z]. Alhoewel dit CSP erg eenvoudig is, verschilt het in essentie niet van het eerdere voorbeeld omtrent havenroosters. Dit eerste voorbeeld bevat slechts meer variabelen, domeinen en constraints, waardoor het omvangrijker is.

Oplossingen

Een oplossing van een CSP voldoet aan het volgende: iedere variabele is geïnitialiseerd met een waarde uit zijn domein, en aan iedere constraint wordt voldaan. Hierbij kan het doel zijn om slechts één (random) oplossing te vinden, alle oplossingen, of een optimale oplossingen (met betrekking tot een kostenfunctie die gerelateerd is aan de waarden die de variabelen van het CSP hebben).

Een mogelijke oplossing van het voorgenoemde CSP is: X = 4, Y = 6, Z = 5. Gezien de beperkte omvang kan dit CSP zonder geavanceerdere algoritmes worden, en zal een basale brute force aanpak afdoende zijn. Dit is echter niet het geval bij een real-world CSP, waarbij het aantal variabelen en constraints vele malen groter is. Het probleem bij real-world CSP’s bevindt zich altijd in de aantallen, waarbij, mede vanwege combinatorial explosion, een brute force aanpak niet zal werken.

Hetzelfde geldt voor backtracking en andere systematische zoekalgoritmes. Backtracking is een efficiëntere manier van zoeken dan brute force, en is in feite niets anders dan depth-first search. Gedurende het zoeken (i.e., toekennen van waarden aan variabelen, zonder dat constraints geschonden worden), zal het algoritme terugkeren (‘backtracken’) naar het vorige keuzepunt in de zoekboom  wanneer een ongeldige oplossing is gevonden, en zal het volgende alternatief bij dat keuzepunt geprobeerd worden. Wanneer deze alternatieven geprobeerd zijn en geen oplossing is gevonden, zal het algoritme wederom terugkeren naar het vorige (hoger gelegen) keuzepunt en daar het volgende alternatief proberen. Indien er geen keuzepunten meer zijn en geen oplossing gevonden is, heeft de zoekactie gefaald. Alhoewel deze aanpak efficiënter is dan generate-and-test, is het verre van adequaat om real-world CSP’s op te lossen binnen een acceptabele tijd.

Constraint Satisfaction Problems Oplossen

Overzicht
Als gevolg van de voorgenoemde problemen omtrent het oplossen van CSP’s zijn uitgebreide algoritmes, heuristieken en strategieën ontwikkeld die in staat zijn om real-world CSP’s binnen een acceptabele tijd op te lossen, waarvan een aantal belangrijke hieronder besproken worden.

Systematic Search
Systematische zoekalgoritmes zijn ondermeer generate-and-test en backtracking, alsmede variaties daarop. Zoals genoemd zijn deze algoritmes op zichzelf verre van adequaat voor real-world CSP’s. Zij worden echter wel gebruikt als basis voor meer geavanceerde algoritmes, waarover hieronder meer.

Consistency Techniques
Consistency techniques vormen effectieve strategieën bij het oplossen van complexe zoekproblemen, en worden gebruikt om de zoekboom van diens rotte takken te ontdoen voordat die zoekboom daadwerkelijk doorzocht wordt. Met andere woorden, toekenningen van waarden aan variabelen uit diens domeinen die a priori als ongeldig herkend worden, worden uit de zoekruimte verwijderd, waardoor deze verkleind wordt. Consistency techniques zijn deterministisch en worden uitgevoerd voordat de daadwerkelijke (non-deterministische) zoekalgoritmes uitgevoerd worden.

Constraint Propagation
Constraint propagation algoritmes zijn zoekalgoritmes die de eigenschappen van constraints propageren in de zoekruimte terwijl het zoeken plaatsvindt.

Een backtracking-algoritme instantieert de variabelen van een CSP stuk voor stuk, waarbij de waarden uit de domeinen van die variabelen gebruikt worden. Hierbij wordt incrementeel getest of aan alle constraints tot dusver voldaan wordt. Wanneer een constraint geschonden wordt (als gevolg van een ongeldige instantiëring van een variabele), dan zal het backtracking-algoritme dit detecteren op het moment dat het gebeurt, en zal het algoritme terugkeren (backtracken) naar het voorgaande keuzepunt in de zoekboom waar alles nog OK was. Vanaf dat keuzepunt gaat het algoritme een andere tak van de zoekboom in, en dit proces gaat zo door totdat alle variabelen geïnstantieerd zijn en geen constraints geschonden zijn.

Hoewel deze basale strategie veel efficiënter is dan de volledige brute-force generate-and-test aanpak, is het probleem dat schendingen van constraints pas gedetecteerd worden wanneer ze plaatsvinden, waarna het algoritme zichzelf moet herstellen door naar een vorige toestand van de zoekruimte terug te keren, en vervolgens een alternatieve route geprobeerd moet worden. Als gevolg hiervan moeten nog steeds zeer veel (kostbare) zoekinspanningen geleverd worden.

Dit kan opgelost worden door mogelijke toekomstige conflicten (schendingen van constraints) in een zoekruimte te voorkomen, wat veel efficiënter is dan constant achteráf moeten herstellen van conflicten. Een constraint propagation strategie die dit doet is ‘forwarding checking’. Constraint propagation is gebaseerd op backtracking, waarbij, zodra een variabele tijdens het zoeken geïnstantieerd wordt, elke waarde uit het domein van een ‘toekomstige’ (nog niet geïnstantieerde) variabele die in conflict is met de huidige instantiëring (tijdelijk) verwijderd wordt uit dat domein van die (nog te bezoeken) variabele. Zodra het domein van zo’n toekomstige variabele leeg is, weet het algoritme dat de huidige (partiële) oplossing ongeldig (inconsistent) is. Als gevolg hiervan ontdoet een forward checking algoritme een zoekboom eerder van rotte takken dan het geval is bij backtracking, waardoor het zoekproces veel efficiënter plaatsvindt.

Variable & Value Ordering
Binnen CSP zoekalgoritmes dient de volgorde waarin variabelen binnen de zoekboom bezocht worden gespecificeerd te worden, alsmede de volgorde waarin waarden uit diens domeinen toegekend worden aan de variabelen. Deze volgordes hebben impact op de efficiëntie van de zoekalgoritmes.

Met betrekking tot de volgorde waarin variabelen bezocht worden (variable ordering) bestaan twee types: static ordering (van tevoren gespecificeerd) en dynamic ordering (het kiezen van de volgende te bezoeken variabele is afhankelijk van de huidige stand van de zoekruimte).

Een heuristiek (vuistregel) die gebruikt wordt bij dynamic variable ordering, wat ondermeer bij het eerdergenoemde forward checking algoritme van toepassing is, is het zogenaamde ‘’first-fail principe’, dat het volgende stelt: “om te slagen, probeer eerst daar waar de kans op falen het grootst is”. Hierbij wordt de variabele met de minst resterende alternatieven  (waarden) geselecteerd als eerstvolgende variabele om te instantiëren. De aanname hierbij is dat elke waarde een even grote kans heeft om onderdeel te zijn van een oplossing, dus hoe meer waarden er zijn, hoe groter de kans dat een van hen succesvol zal zijn. Echter, de reden om de variabele te kiezen met de minst resterende waarden is dat (binnen de context van forward checking) indien de huidige (partiële) oplossing niet zal leiden tot een volledige oplossing, dit beter vroeger dan later ontdekt kan worden. Het first-fail principe tracht derhalve de gemiddelde diepte van de takken in de zoekboom te verkleinen door vroegtijdige fouten te triggeren.

Soortgelijke strategieën en heuristieken bestaan ook voor value ordering, met betrekking de volgorde waarin waarden toegekend worden aan de volgende te instantiëren variabele.

CSP Frameworks

Overzicht
Binnen de voorgaande secties is ingegaan op algoritmes en strategieën waarmee CSPs efficiënt en binnen een acceptabele tijd opgelost kunnen worden. Deze algoritmes, en alle varianten hierop, kunnen geïmplementeerd worden op basis van deze informatie en alles wat hierover beschikbaar is via bijvoorbeeld het WWW.

Daarnaast zijn er diverse CSP frameworks ontwikkeld die off-the-shelf faciliteiten bieden voor het efficiënt modelleren en oplossen van CSP’s.

ILOG
Het meest gebruikte commerciële CSP framework is ILOG, wat ondermeer ook specifieke modules bevat voor rooster- en planningsproblemen. ILOG is ondermeer beschikbaar voor het Java-platform.

Open-Source
Tevens zijn er diverse open-source Java CSP frameworks beschikbaar, waarvan er een – het Choco CSP framework – kort besproken wordt.

Het open-source Choco CSP framework (beschikbaar via Sourceforge) is ontwikkeld in Java, en vergemakkelijkt het modelleren van CSP’s doordat een abstractielaag aan de gebruiker (software engineer) geboden wordt. Tevens biedt het off-the-shelf CSP-algoritmes, waarmee de gemodelleerde CSP’s opgelost kunnen worden. Men kan er eenvoudig variabelen, domeinen en constraints mee definiëren, en vervolgens de resulterende CSP’s mee oplossen. Choco is in staat om één oplossing voor een probleem te vinden, alle oplossingen, of een optimale oplossing.

N-Queens
Als voorbeeld zal een klassiek CSP besproken worden: het N-queens probleem. Hierbij is het doel om N koninginnen op een N x N schaakbord te plaatsen, zodanig dat geen enkele koningin door een andere koningin geslagen kan worden (gebruik makend van de standaard schaakregels). Een oplossing betekent derhalve dat geen enkele koningin een rij, kolom of diagonaal met een andere koningin mag delen.

Het N-queens probleem is eenvoudig te begrijpen, maar bevat tegelijkertijd een hoge mate van (rekentechnische) complexiteit. Zo heeft het 8-queens probleem 283.274.583.552 (64x63x..x58x57/8!) mogelijke oplossingen, waarvan er slechts 92 geldig zijn (en waarvan er slechts 12 uniek zijn).

Middels het Choco framework wordt het 8-queens probleem als volgt gemodelleerd en opgelost:

// Creëer een leeg CSP-object 
AbstractProblem CSP = new Problem();

// Creëer en initialiseer de benodigde variabelen met bijbehorende domeinen
int n = 8;
IntVar[] queens = new IntVar[n];

for (int i = 0; i < n; i++)
{
queens[i] = CSP.makeEnumIntVar("Q" + i, 1, n);
}

// Voeg de constraints toe (van het type (not-equals (neq)):
// koninginnen mogen zich niet op dezelfde rijen, kolommen en diagonalen bevinden
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++) {
int k = j - i;

CSP.post(CSP.neq(queens[i], queens[j]));
CSP.post(CSP.neq(queens[i], CSP.plus(queens[j], k)));
CSP.post(CSP.neq(queens[i], CSP.minus(queens[j], k)));
}
}

// Vind alle oplossingen
CSP.solveAll();

// En geef (bijvoorbeeld) aan hoeveel oplossingen er gevonden zijn
System.out.println("NbSol: " + CSP.getSolver().getNbSolutions());

Het framework geeft als resultaat aan dat alle 92 oplossingen gevonden zijn.

Dit is een eenvoudig voorbeeld van hoe een CSP efficiënt gemodelleerd en opgelost kan worden in Java middels het open-source Choco CSP framework. Met een dergelijk framework hoeft een software engineer zich niet bezig te houden met het creëren van CSP-algoritmes of de infrastructuur waarmee variabelen, domeinen en constraints gecreëerd kunnen worden, maar kan men zich direct focussen op het probleem dat opgelost moet worden, waarbij een uitgebreide abstractielaag en off-the-shelf CSP-algoritmes gebruikt (en waar gewenst uitgebreid) kunnen worden.

Auteur: Nico van Hanxleden Houwert is Solutions Architect bij IPROFS.