POLITECHNIKA WARSZAWSKA
MEL
MEL
WYDZIAA
MECHANICZNY ENERGETYKI I LOTNICTWA
WPROWADZENIE
DO SZTUCZNEJ INTELIGENCJI
NS 586
Dr in\
. Franciszek Dul
� F.A. Dul 2007
5. ROZWI
ZYWANIE
PROBLEMÓW Z OGRANICZENIAMI
PROBLEMÓW Z OGRANICZENIAMI
� F.A. Dul 2007
Problemy z ograniczeniami
Poka\
emy, w jaki sposób agent mo\
e
osiągnąć zamierzony cel je\
eli musi
uwzględniać ograniczenia występujące
w zadaniu.
w zadaniu.
� F.A. Dul 2007
5.1. Wprowadzenie
Plan rozdziału
" Zadania z ograniczeniami.
" Poszukiwanie wsteczne dla zadań z ograniczeniami.
" Poszukiwania lokalne dla zadań z ograniczeniami.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami (CSP)
Ró\
nica między zadaniami poszukiwania a zadaniami
z ograniczeniami (Constraint Satisfaction Problems):
" w zadaniach zwykłych stan mo\
e być dowolną strukturą
która umo\
liwia wyznaczanie następników, obliczenie
funkcji kosztu, sprawdzenie osiągnięcia celu;
" w zadaniach z ograniczeniami:
 stan jest zbiorem zmiennych Xi przyjmujących wartości
z dziedzin Di,
 cel zdefiniowany jest poprzez ogranicznia C które muszą
 cel zdefiniowany jest poprzez ogranicznia Ci, które muszą
spełniać wartości zmiennych stanu, np. C2,: X1 e" X2
Przypisanie wartości zmiennym stanu jest zgodne, je\
eli
nie narusza ograniczeń.
Rozwiązaniem zadania z ograniczeniami jest zgodny zbiór
wartości zmiennych stanu spełniający wszystkie ograniczenia.
Przykłady:
" kolorowanie map,
" kompozycja parkietów,
" kryptografia,
� F.A. Dul 2007
" szeregowanie obserwacji dla teleskopu Hubble a.
5.1. Zadania z ograniczeniami
Zadania z ograniczeniami
Charakterystyczne cechy zadań z ograniczeniami:
" standardowy sposób sformułowania;
" standardowe postacie funkcji następstwa i funkcji celu;
" standardowe heurystyki, niezale\
ne od charakteru
konkretnego zadania.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Przykład - kolorowanie mapy
" Zmienne: WA, NT, Q, NSW, V, SA, T
" Dziedziny: Di = {R,G,B} ( = {Red,Green,Blue} )
" Ograniczenia: obszary przyległe muszą mieć ró\
ne kolory
 WA `" NT, lub
 (WA,NT) " { (R,G), (R,B), (G,R), (G,B), (B,R), (B,G) }
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Przykład - kolorowanie mapy
Rozwiązaniem jest ka\
de kompletne i zgodne przypisanie
wartości z dziedzin zmiennym stanu, np.:
WA = R, NT = G, Q = R, NSW = G, V = R, SA = B, T = G
& ale rozwiązaniem jest równie\
np.
WA = G, NT = B, Q = G, NSW = B, V = G, SA = R, T = B
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Graf ograniczeń
Binarne zadanie z ograniczeniami: ka\
de ograniczenie
jest relacją dwóch zmiennych.
Graf ograniczeń: węzły są zmiennymi,
krawędzie są ograniczeniami.
Sformułowanie w postaci grafu pozwala uprościć
poszukiwanie rozwiązania.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Odmiany zadań CSP
Dyskretne zmienne stanu.
" dziedziny skończone:
 n zmiennych, wymiar d �! O(dn) mo\
liwych przypisań;
np.: zadania boolowskie;
" dziedziny nieskończone:
" liczby naturalne, łańcuchy,
" np. planowanie (kolejkowanie) zadań,
" wymagają języka do opisu ograniczeń, np.
" wymagają języka do opisu ograniczeń, np.
StartJob1 + 5 e" StartJob3
" rozwiązywalne z ograniczeniami liniowymi;
z nieliniowymi - nierozstrzygalne;
Ciągłe zmienne stanu.
" np. czasy rozpoczęcia i zakończenia obserwacji przez
teleskop Hubble a;
" zadania z ograniczeniami liniowymi są rozwiązywalne
za pomocą programowania liniowego w czasie
wielomianowym.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Odmiany ograniczeń w zadaniach CSP
Ograniczenia unarne (dla pojedyńczych zmiennych stanu).
" np. SA `" Red
Ograniczenia binarne (dla dwóch zmiennych stanu).
" np. SA `" WA
Ograniczenia wy\
szego rzędu, dla trzech lub większej liczby
zmiennych stanu
" np. dla kolumny danych kryptoarytmetycznych
" np. dla kolumny danych kryptoarytmetycznych
Ograniczenia preferencyjne (miękkie), np.
czerwony kolor jest lepszy ni\
zielony;
Często są reprezentowane poprzez koszt przypisania
wartości do zmiennej;
Zadanie jest wtedy typu optymalizacji z ograniczeniami.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Przykład - arytmetyka kryptograficzna
Znalez
ć cyfry, które przyporządkowane literom w sposób
jednoznaczny spełnią równanie
Graf zadania
" Zmienne: F, T, U, W, R, O, X1 , X2 , X3 ,
" Dziedziny: {0,1,2,3,4,5,6,7,8,9}
" Ograniczenia: F, T, U, W, R, O są ró\
nymi cyframi oraz:
" O + O = R + 10 � X1 ,
" X1 + W + W = U + 10 � X2 ,
" X2 + T + T = O + 10 � X3,,
" X3 = F, T `" 0, F `" 0.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Zadania CSP w praktyce
Zadania przyporządkowania.
" np. kto prowadzi jaki wykład?
Zadania rozkładu zajęć (timetabling)
" np. które zajęcia w której sali i kiedy?
Zadania planowania (szeregowania) w transporcie,
przemyśle, itp.
W zadaniach praktycznych zmienne przyjmują często
wartości ciągłe rzeczywiste.
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
CSP jako standardowe zadanie poszukiwania
Zadanie CSP mo\
e być zawsze sformułowane w postaci
standardowej jako zadanie poszukiwania.
Sformułowanie przyrostowe
" Stan początkowy = przypisanie puste { };
" Funkcja następnika: przypisać wartość wolnej zmiennej
pod warunkiem, \
e nie spowoduje to naruszenia
ograniczeń;
" Test celu: kompletność bie\
ącego przypisania;
" Test celu: kompletność bie\
ącego przypisania;
" Koszt drogi: stały w ka\
dym kroku;
Sformułowanie to jest identyczne dla wszystkich zadań CSP.
Rozwiązanie zadania CSP uzyskuje się po n krokach
- mo\
na więc u\
yć algorytmu poszukiwania w głąb.
Droga rozwiązania jest nieistotna, mo\
na więc u\
yć
kompletnej reprezentacji stanu.
W kroku l-tym b = (n-l)d, zatem istnieje a\
n! dn liści drzewa
(mimo, \
e jest tylko dn ró\
nych stanów).
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Przypisanie wartości jest przemienne, np.:
[ WA = R �! NT = G ] a" [ NT = G �! WA = R ]
W ka\
dym węz
le przypisuje się jedną spośród d wartości
do jednej zmiennej, zatem b = d i powstaje tylko dn liści
drzewa.
Algorytm szukania w głąb zastosowany do zadania CSP
z przypisaniem wartości jednej zmiennej nazywa się
poszukiwaniem wstecznym (backtracking search).
poszukiwaniem wstecznym (backtracking search).
Idea: przypisuje się wartość jednej zmiennej i cofa się
działanie gdy kolejnej zmiennej nie mo\
na przypisać
\
adnej wartości bez naruszenia ograniczeń.
Poszukiwanie wsteczne jest podstawowym algorytmem
nieinformowanym dla zadań CSP.
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Algorytm rekursywny poszukiwania wstecznego CSP
function BACKTRACKING-SEARCH(csp) return a solution or failure
return RECURSIVE-BACKTRACKING({} , csp)
function RECURSIVE-BACKTRACKING(assignment, csp) return a solution or failure
if assignment is complete then return assignment
var �! SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
if value is consistent with assignment according to CONSTRAINTS[csp] then
if value is consistent with assignment according to CONSTRAINTS[csp] then
add {var=value} to assignment
result �! RRECURSIVE-BACTRACKING(assignment, csp)
if result `" failure then return result
remove {var=value} from assignment
return failure
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Przykład - kolorowanie mapy
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Przykład - kolorowanie mapy
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Przykład - kolorowanie mapy
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Przykład - kolorowanie mapy
� F.A. Dul 2007
5.1. Zadania z ograniczeniami
Poprawa efektywności poszukiwania wstecznego
Efektywność algorytmu ogólnego mo\
e być zasadniczo
poprawiona poprzez rozstrzygnięcie następujących kwestii:
" która zmienna powinna być sprawdzana w następnej
kolejności?
" w jakiej kolejności nale\
y przyporządkowywać wartości
zmiennej?
" czy mo\
na wykryć nieuniknione niepowodzenie?
" czy mo\
na wykorzystać znajomość struktury zadania?
" czy mo\
na wykorzystać znajomość struktury zadania?
Istnieją następujące strategie poszukiwania wstecznego:
" najbardziej ograniczonej zmiennej (most constrained
variable),
" najmniej ograniczającej wartości (least constraining
value),
" sprawdzania w przód (forward checking).
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Strategia najbardziej ograniczonej zmiennej
Idea: wybrać zmienną której mo\
na przypisać najmniej
wartości dopuszczalnych.
Wersja heurystyczna nosi nazwę minimum pozostałych
wartości (minimum remaining values).
wartości (minimum remaining values).
Strategia najbardziej ograniczającej zmiennej
Idea: wybrać zmienną której nakłada najwięcej ograniczeń
na pozostałe zmienne.
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Heurystyka stopniowa
Idea: wybrać zmienną która występuje w największej liczbie
ograniczeń nało\
onychna inną wolną zmienną.
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Strategia najmniej ograniczającej wartości
Idea: wybrać dla zmiennej bie\
ącej taką wartość, która
pozostawia największą swobodę przy przypisywaniu
wartości pozostałym wolnym zmiennym.
pozostawia 1
wartość dla SA
pozostawia 0
wartości dla SA
wartości dla SA
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Strategia sprawdzania w przód
Idea:
" śledzić dopuszczalne wartości dla wolnych zmiennych;
" przerwać dalsze przypisywanie je\
eli jakiejś zmiennej
nie mo\
na będzie przypisać \
adnej wartości
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Strategia sprawdzania w przód
Idea:
" śledzić dopuszczalne wartości dla wolnych zmiennych;
" przerwać dalsze przypisywanie je\
eli jakiejś zmiennej
nie mo\
na będzie przypisać \
adnej wartości
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Strategia sprawdzania w przód
Idea:
" śledzić dopuszczalne wartości dla wolnych zmiennych;
" przerwać dalsze przypisywanie je\
eli jakiejś zmiennej
nie mo\
na będzie przypisać \
adnej wartości
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Strategia sprawdzania w przód
Idea:
" śledzić dopuszczalne wartości dla wolnych zmiennych;
" przerwać dalsze przypisywanie je\
eli jakiejś zmiennej
nie mo\
na będzie przypisać \
adnej wartości
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Propagacja ograniczeń
Połączenie heurystyki i sprawdzania w przód zapewani
większą efektywność ni\
stosowanie ich oddzielnie.
Sprawdzanie w przód propaguje informację ze zmiennych
zajętych do wolnych.
Nie zapewnia to jednak odpowiednio wczesnego wykrywania
wszystkich niepowodzeń.
" NT i SA nie mogą być pomalowane na niebiesko.
Propagacja ograniczeń wymusza spełnienie ograniczeń
tylko lokalnie.
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Zgodność krawędzi
Połączenie heurystyki i sprawdzania w przód zapewnia
większą efektywność ni\
stosowanie ich oddzielnie.
Krawędz
łącząca zmienne X oraz Y jest zgodna wtedy i tyko
wtedy, gdy dla ka\
dej dopuszczalnej wartości x zmiennej X
istnieje dopuszczalna wartość y dla zmiennej Y.
" Krawędz
SA NSW jest zgodna, gdy\
SA = B �! NSW = R



" Krawędz
NSW SA nie jest zgodna, gdy\




NSW = R �! SA = B, ale NSW = B �! SA = ?
Krawędz
NSW SA stanie się zgodna, je\
eli z NSW usunie się B.



" Po usunięciu wartości nale\
y sprawdzić sąsiadów; z V usunąć R.
� F.A. Dul 2007
5.2. Poszukiwanie wsteczne
Algorytm zgodności krawędzi
function AC-3(csp) return the CSP, possibly with reduced domains
inputs: csp, a binary csp with variables {X1, X2, & , Xn}
local variables: queue, a queue of arcs initially the arcs in csp
while queue is not empty do
(Xi, Xj) �! REMOVE-FIRST(queue)
if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then
for each Xk in NEIGHBORS[Xi ] do
add (Xi, Xj) to queue
add (Xi, Xj) to queue
function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we
remove a value
removed �! false
for each x in DOMAIN[Xi] do
if no value y in DOMAIN[Xi] allows (x,y) to satisfy the constraints
between Xi and Xj
then delete x from DOMAIN[Xi]; removed �! true
return removed
Czas obliczeń ~O(n2d3)
� F.A. Dul 2007
5.3. Poszukiwania lokalne dla zadań CSP
Algorytmy poszukiwań lokalnych (najszybszego wzrostu,
symulowane wy\
arzanie) działają na stanach  kompletnych ,
tj. takich w których wszystkie zmienne mają przypisane
wartości.
Aby mo\
na było je zastosować do zadań CSP nale\
y:
" dopuścić stany w których ograniczenia nie są
spełnione,
" wprowadzić operatory które zmieniają przypisania
" wprowadzić operatory które zmieniają przypisania
wartości do zmiennych
wartości do zmiennych
Wybór zmiennych: selekcja losowa zmiennej będącej
w konflikcie inną zmienną.
Wyboru wartości dokonuje się za pomocą heurystyki
minimalnych konfliktów:
 wybrać wartość która powoduje najmniejszą liczbę
konfliktów z innymi zmiennymi.
Np. algorytm najszybszego wzrostu z heurystyką
h(n) = całkowita liczba naruszonych ograniczeń.
� F.A. Dul 2007
5.3. Poszukiwania lokalne dla zadań CSP
Przykład - problem czterech królowych
" Stan: cztery królowe w czterech kolumnach (44 = 256 stanów)
" Działania: ruch królowej w kolumnie
" Test celu: \
adna królowa nie jest atakowana
" Heurystyka: h(n) = liczba atakowanych królowych
Dla zadanego losowo stanu początkowego algorytm potrafi
rozwiązać problem n królowych dla bardzo wielkich n, np.
n=10,000,000 przy prawie takim samym czasie obliczeń.
� F.A. Dul 2007
5.3. Poszukiwania lokalne dla zadań CSP
Zalety poszukiwań lokalnych dla zadań CSP
" Czas rozwiązania zadania CSP przy u\
yciu poszukiwań
lokalnych jest prawie niezale\
ny od wymiaru zadania
(por. zadanie n królowych);
" Algorytmy poszukiwań lokalnych mogą być zastosowane
w trybie online - w przeciwieństwie do algorytmu
backtracking.
� F.A. Dul 2007
Podsumowanie
" Poszukiwania z ograniczeniami (Constrained Search
Problems) stanowią szczególny rodzaj zadań:
" stan jest zbiorem zmiennych którym przypisane są wartości
z określonego zbioru - dziedziny,
" cel zdefiniowany jest poprzez ograniczenia nało\
one na wartości
zmiennych;
" Metoda poszukiwania wstecznego (backtracking)
to poszukiwania w głąb z przypisaniem w ka\
dym węz
le
wartości tylko jednej zmiennej.
wartości tylko jednej zmiennej.
" Uporządkowanie zmiennych i dobre heurystyki wyboru
wartości znacznie poprawiają efektywność metody
poszukiwania wstecznego.
" Metoda sprawdzania w przód pozwala zmniejszyć ryzyko
niepowodzenia w dalszym etapie rozwiązywania zadania.
" Algorytmy propagacji ograniczeń (np. algorytm zgodności
krawędzi) pozwalają na wykrycie póz
nych niezgodności.
" Algorytm minimalnych konfliktów jest bardzo efektywny
przy rozwiązywaniu zadań praktycznych.
� F.A. Dul 2007