AI_5_1

Problemy z ograniczeniami

Poka

emy, w jaki sposób agent mo

osi

ąć

zamierzony cel je

eli musi

uwzgl

dnia

ograniczenia wyst

puj

w zadaniu.

© F.A. Dul 2007

w zadaniu.

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

przyjmuj

cych

warto

dziedzin

– cel zdefiniowany jest poprzez

ogranicznia

C które musz

© F.A. Dul 2007

– cel zdefiniowany jest poprzez

ogranicznia

które musz

spełnia

warto

ci zmiennych stanu, np. C

: X

≥

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

5.1. Zadania z ograniczeniami

Przykład - kolorowanie mapy

© F.A. Dul 2007

• Zmienne:

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

• Dziedziny:

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

poszukiwanie rozwi

zania.

Odmiany zada

CSP

Dyskretne zmienne stanu.

5.1. Zadania z ograniczeniami

• dziedziny sko

czone:

– n zmiennych, wymiar

d ⇒ O(d

)

liwych przypisa

;

np.: zadania boolowskie;

• dziedziny niesko

czone:

• liczby naturalne, ła

cuchy,

• np. planowanie (kolejkowanie) zada

• wymagaj

zyka do opisu ogranicze

, np.

© F.A. Dul 2007

głe zmienne stanu.

• wymagaj

zyka do opisu ogranicze

, np.

StartJob

+ 5

≥

StartJob

• 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

≠

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;

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

, X

• 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

• X

+ W + W = U + 10 · X

• X

+ T + T = O + 10 · X

• X

= F, T

≠

0, F

≠

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

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

algorytmu poszukiwania w gł

Droga rozwi

zania jest nieistotna, mo

na wi

c u

kompletnej reprezentacji stanu.

W kroku l-tym b = (n-l)d, zatem istnieje a

n! d

ci drzewa

(mimo,

e jest tylko d

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

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

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

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

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

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

© 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

© 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

© 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

© F.A. Dul 2007

Propagacja ogranicze

5.2. Poszukiwanie wsteczne

Poł

czenie heurystyki i sprawdzania w przód zapewani

ksz

efektywno

ść

stosowanie ich oddzielnie.

Nie zapewnia to jednak odpowiednio wczesnego wykrywania

wszystkich niepowodze

Sprawdzanie w przód propaguje informacj

ze zmiennych

zaj

tych do wolnych.

• NT i SA nie mog

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

ksz

efektywno

ść

stosowanie ich oddzielnie.

Kraw

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

→

NSW jest zgodna, gdy

SA = B

⇒

NSW = R

Kraw

NSW

→

SA stanie si

zgodna, je

eli z NSW usunie si

• Kraw

NSW

→

SA nie jest zgodna, gdy

NSW = R

⇒

SA = B, ale NSW = B

⇒

SA = ?

• Po usuni

ciu warto

ci nale

y sprawdzi

siadów; z V usun

ąć

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

, X

, …, X

}

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

while queue is not empty do

, X

)

←

REMOVE-FIRST(queue)

if REMOVE-INCONSISTENT-VALUES(X

, X

) then

for each X

in NEIGHBORS[X

] do

add (X

, X

) to queue

add (X

, X

) to queue

function REMOVE-INCONSISTENT-VALUES(X

, X

) return true iff we

remove a value
removed

←

false

for each x in DOMAIN[X

] do

if no value y in DOMAIN[X

] allows (x,y) to satisfy the constraints

between X

and X

then delete x from DOMAIN[X

]; removed

←

true

return removed

Czas oblicze

~O(n

)

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

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

• wprowadzi

operatory które zmieniaj

przypisania

warto

ci do zmiennych

Wybór zmiennych: selekcja losowa zmiennej b

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

= 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

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

zastosowane

w trybie online - w przeciwie

stwie do algorytmu

backtracking.

Podsumowanie

• Poszukiwania z ograniczeniami (Constrained Search

Problems) stanowi

szczególny rodzaj zada

• stan jest zbiorem zmiennych którym przypisane s

warto

z okre

lonego zbioru - dziedziny,

• cel zdefiniowany jest poprzez ograniczenia nało

one na warto

zmiennych;

• Metoda poszukiwania wstecznego (backtracking)

to poszukiwania w gł

b z przypisaniem w ka

dym w

ęź

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

kraw

dzi) pozwalaj

na wykrycie pó

nych niezgodno

ci.

• Algorytm minimalnych konfliktów jest bardzo efektywny

przy rozwi

zywaniu zada

praktycznych.