WPROWADZENIE

DO SZTUCZNEJ INTELIGENCJI

POLITECHNIKA WARSZAWSKA

WYDZIAŁ MECHANICZNY ENERGETYKI I LOTNICTWA

MEL

MEL

NS 586

Dr in

ż

. Franciszek Dul

© F.A. Dul 2007

5. ROZWIĄZYWANIE

PROBLEMÓW Z OGRANICZENIAMI

© F.A. Dul 2007

PROBLEMÓW Z OGRANICZENIAMI

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.

© F.A. Dul 2007

w zadaniu.

5.1. Wprowadzenie

• Zadania z ograniczeniami.

• Poszukiwanie wsteczne dla zada

ń

z ograniczeniami.

• Poszukiwania lokalne dla zada

ń

z ograniczeniami.

Plan rozdziału

© 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 X

i

przyjmuj

ą

cych

warto

ś

ci

z

dziedzin

D

i,

– cel zdefiniowany jest poprzez

ogranicznia

C które musz

ą

© F.A. Dul 2007

– cel zdefiniowany jest poprzez

ogranicznia

C

i,

które musz

ą

spełnia

ć

warto

ś

ci zmiennych stanu, np. C

2,

: X

1

≥

X

2

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,
• szeregowanie obserwacji dla teleskopu Hubble’a.

Przypisanie warto

ś

ci zmiennym stanu jest zgodne, je

ż

eli

nie narusza ogranicze

ń

.

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.

5.1. Zadania z ograniczeniami

© F.A. Dul 2007

5.1. Zadania z ograniczeniami

Przykład - kolorowanie mapy

© F.A. Dul 2007

• Zmienne:

WA, NT, Q, NSW, V, SA, T

• Dziedziny:

D

i

= {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) }

Przykład - kolorowanie mapy

5.1. Zadania z ograniczeniami

© F.A. Dul 2007

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

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.

5.1. Zadania z ograniczeniami

© F.A. Dul 2007

Sformułowanie w postaci grafu pozwala upro

ś

ci

ć

poszukiwanie rozwi

ą

zania.

Odmiany zada

ń

CSP

Dyskretne zmienne stanu.

5.1. Zadania z ograniczeniami

• dziedziny sko

ń

czone:

– n zmiennych, wymiar

d ⇒ O(d

n

)

mo

ż

liwych przypisa

ń

;

np.: zadania boolowskie;

• dziedziny niesko

ń

czone:

• liczby naturalne, ła

ń

cuchy,

• np. planowanie (kolejkowanie) zada

ń

,

• wymagaj

ą

j

ę

zyka do opisu ogranicze

ń

, np.

© F.A. Dul 2007

Ci

ą

głe zmienne stanu.

• wymagaj

ą

j

ę

zyka do opisu ogranicze

ń

, np.

StartJob

1

+ 5

≥

StartJob

3

• rozwi

ą

zywalne z ograniczeniami liniowymi;

z nieliniowymi - nierozstrzygalne;

• 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.

Odmiany ogranicze

ń

w zadaniach CSP

Ograniczenia unarne (dla pojedy

ń

czych zmiennych stanu).

5.1. Zadania z ograniczeniami

• 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

© F.A. Dul 2007

• 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.

5.1. Zadania z ograniczeniami

Przykład - arytmetyka kryptograficzna

Znale

źć

cyfry, które przyporz

ą

dkowane literom w sposób

jednoznaczny spełni

ą

równanie

© F.A. Dul 2007

• Zmienne:

F, T, U, W, R, O, X

1

, X

2

, X

3

,

• 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 · X

1

,

• X

1

+ W + W = U + 10 · X

2

,

• X

2

+ T + T = O + 10 · X

3,

,

• X

3

= F, T

≠

0, F

≠

0.

Graf zadania

Zadania CSP w praktyce

Zadania przyporz

ą

dkowania.

5.1. Zadania z ograniczeniami

• 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.

© F.A. Dul 2007

W zadaniach praktycznych zmienne przyjmuj

ą

cz

ę

sto

warto

ś

ci ci

ą

głe rzeczywiste.

CSP jako standardowe zadanie poszukiwania

Zadanie CSP mo

ż

e by

ć

zawsze sformułowane w postaci

standardowej jako zadanie poszukiwania.

5.1. Zadania z ograniczeniami

• 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;

Sformułowanie przyrostowe

© F.A. Dul 2007

• 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! d

n

li

ś

ci drzewa

(mimo,

ż

e jest tylko d

n

ró

ż

nych stanów).

5.2. Poszukiwanie wsteczne

Algorytm szukania w gł

ą

b zastosowany do zadania CSP

z przypisaniem warto

ś

ci jednej zmiennej nazywa si

ę

poszukiwaniem wstecznym (backtracking search).

Przypisanie warto

ś

ci jest przemienne, np.:

[ WA = R

⇒

NT = G ]

≡

[ NT = G

⇒

WA = R ]

W ka

ż

dym w

ęź

le przypisuje si

ę

jedn

ą

spo

ś

ród d warto

ś

ci

do jednej zmiennej, zatem b = d i powstaje tylko d

n

li

ś

ci

drzewa.

© F.A. Dul 2007

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.

Algorytm rekursywny poszukiwania wstecznego CSP

5.2. Poszukiwanie wsteczne

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

© F.A. Dul 2007

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

Przykład - kolorowanie mapy

5.2. Poszukiwanie wsteczne

© F.A. Dul 2007

Przykład - kolorowanie mapy

5.2. Poszukiwanie wsteczne

© F.A. Dul 2007

Przykład - kolorowanie mapy

5.2. Poszukiwanie wsteczne

© F.A. Dul 2007

Przykład - kolorowanie mapy

5.2. Poszukiwanie wsteczne

© F.A. Dul 2007

Poprawa efektywno

ś

ci poszukiwania wstecznego

Efektywno

ść

algorytmu ogólnego mo

ż

e by

ć

zasadniczo

poprawiona poprzez rozstrzygni

ę

cie nast

ę

puj

ą

cych kwestii:

5.1. Zadania z ograniczeniami

• 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?

© F.A. Dul 2007

• 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).

Strategia najbardziej ograniczonej zmiennej

Idea: wybra

ć

zmienn

ą

której mo

ż

na przypisa

ć

najmniej

warto

ś

ci dopuszczalnych.

5.2. Poszukiwanie wsteczne

Wersja heurystyczna nosi nazw

ę

minimum pozostałych

warto

ś

ci (minimum remaining values).

© F.A. Dul 2007

warto

ś

ci (minimum remaining values).

Strategia najbardziej ograniczaj

ą

cej zmiennej

Idea: wybra

ć

zmienn

ą

której nakłada najwi

ę

cej ogranicze

ń

na pozostałe zmienne.

Heurystyka stopniowa

5.2. Poszukiwanie wsteczne

Idea: wybra

ć

zmienn

ą

która wyst

ę

puje w najwi

ę

kszej liczbie

ogranicze

ń

nało

ż

onychna inn

ą

woln

ą

zmienn

ą

.

© F.A. Dul 2007

Strategia najmniej ograniczaj

ą

cej warto

ś

ci

5.2. Poszukiwanie wsteczne

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

© F.A. Dul 2007

warto

ś

ci dla SA

Strategia sprawdzania w przód

5.2. Poszukiwanie wsteczne

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

Strategia sprawdzania w przód

5.2. Poszukiwanie wsteczne

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

Strategia sprawdzania w przód

5.2. Poszukiwanie wsteczne

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

Strategia sprawdzania w przód

5.2. Poszukiwanie wsteczne

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

Propagacja ogranicze

ń

5.2. Poszukiwanie wsteczne

Poł

ą

czenie heurystyki i sprawdzania w przód zapewani

wi

ę

ksz

ą

efektywno

ść

ni

ż

stosowanie ich oddzielnie.

Nie zapewnia to jednak odpowiednio wczesnego wykrywania

wszystkich niepowodze

ń

.

Sprawdzanie w przód propaguje informacj

ę

ze zmiennych

zaj

ę

tych do wolnych.

© F.A. Dul 2007

• NT i SA nie mog

ą

by

ć

pomalowane na niebiesko.

Propagacja ogranicze

ń

wymusza spełnienie ogranicze

ń

tylko lokalnie.

Zgodno

ść

kraw

ę

dzi

5.2. Poszukiwanie wsteczne

Poł

ą

czenie heurystyki i sprawdzania w przód zapewnia

wi

ę

ksz

ą

efektywno

ść

ni

ż

stosowanie ich oddzielnie.

Kraw

ę

d

ź

ł

ą

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.

© F.A. Dul 2007

• Kraw

ę

d

ź

SA

→

→

→

→

NSW jest zgodna, gdy

ż

SA = B

⇒

NSW = R

Kraw

ę

d

ź

NSW

→

→

→

→

SA stanie si

ę

zgodna, je

ż

eli z NSW usunie si

ę

B.

• Kraw

ę

d

ź

NSW

→

→

→

→

SA nie jest zgodna, gdy

ż

NSW = R

⇒

SA = B, ale NSW = B

⇒

SA = ?

• Po usuni

ę

ciu warto

ś

ci nale

ż

y sprawdzi

ć

s

ą

siadów; z V usun

ąć

R.

Algorytm zgodno

ś

ci kraw

ę

dzi

5.2. Poszukiwanie wsteczne

function AC-3(csp) return the CSP, possibly with reduced domains

inputs: csp, a binary csp with variables {X

1

, X

2

, …, X

n

}

local variables: queue, a queue of arcs initially the arcs in csp

while queue is not empty do

(X

i

, X

j

)

←

REMOVE-FIRST(queue)

if REMOVE-INCONSISTENT-VALUES(X

i

, X

j

) then

for each X

k

in NEIGHBORS[X

i

] do

add (X

i

, X

j

) to queue

© F.A. Dul 2007

add (X

i

, X

j

) to queue

function REMOVE-INCONSISTENT-VALUES(X

i

, X

j

) return true iff we

remove a value
removed

←

false

for each x in DOMAIN[X

i

] do

if no value y in DOMAIN[X

i

] allows (x,y) to satisfy the constraints

between X

i

and X

j

then delete x from DOMAIN[X

i

]; removed

←

true

return removed

Czas oblicze

ń

~O(n

2

d

3

)

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.

• dopu

ś

ci

ć

stany w których ograniczenia nie s

ą

spełnione,

• wprowadzi

ć

operatory które zmieniaj

ą

przypisania

warto

ś

ci do zmiennych

Aby mo

ż

na było je zastosowa

ć

do zada

ń

CSP nale

ż

y:

© F.A. Dul 2007

• wprowadzi

ć

operatory które zmieniaj

ą

przypisania

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

ń

.

Przykład - problem czterech królowych

5.3. Poszukiwania lokalne dla zada

ń

CSP

• Stan

: cztery królowe w czterech kolumnach (4

4

= 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

© F.A. Dul 2007

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

ń

.

Zalety poszukiwa

ń

lokalnych dla zada

ń

CSP

5.3. Poszukiwania lokalne 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

ęź

le

warto

ś

ci tylko jednej zmiennej.

© F.A. Dul 2007

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ó

ź

nych niezgodno

ś

ci.

• Algorytm minimalnych konfliktów jest bardzo efektywny

przy rozwi

ą

zywaniu zada

ń

praktycznych.