AI_4_1

Poszukiwania informowane

Poka

emy, w jaki sposób agent mo

Poka

emy, w jaki sposób agent mo

osi

ąć

zamierzony cel du

o bardziej

osi

ąć

zamierzony cel du

o bardziej

efektywnie poprzez poszukiwania
wykorzystuj

ce dodatkow

wiedz

wykorzystuj

ce dodatkow

wiedz

na temat zadania.

© F.A. Dul 2007

Niniejszy rozdział po

cony jest agentom celowym,

Wprowadzenie

Niniejszy rozdział po

cony jest agentom celowym,

których działanie oparte jest na poszukiwaniu rozwi

zania

w zbiorze rozwi

dopuszczalnych.

w zbiorze rozwi

dopuszczalnych.

Poszukiwanie informowane (informed search) polega na
znajdywaniu rozwi

zania zadania przy wykorzystaniu innej

znajdywaniu rozwi

zania zadania przy wykorzystaniu innej

dost

pnej wiedzy, specyficznej dla tego zadania.

© F.A. Dul 2007

4.1. Poszukiwania informowane

Poszukiwania nieinformowane stanowi

form

rozwi

zywania

zadania “na o

lep”.

Podstawowym algorytmem strategii nieinformowanych był
algorytm przeszukiwania drzewa - niezbyt efektywny.

Istotn

popraw

efektywno

ci mo

na uzyska

wykorzystuj

dodatkow

informacj

o zadaniu.

dodatkow

informacj

o zadaniu.

Strategie poszukiwania wykorzystuj

ce dodatkowe

informacje o zadaniu nazywa si

(po)informowanymi.

Idea: dodatkowa iInformacja mo

e posłu

najkorzystniej-

informacje o zadaniu nazywa si

(po)informowanymi.

Idea: dodatkowa iInformacja mo

e posłu

najkorzystniej-

szego uporz

dkowania w

złów przed ich rozwini

ciem

© F.A. Dul 2007

4.1. Poszukiwania informowane

Poszukiwanie informowane

Zasada poszukiwania informowanego:

– wybór w

zła do rozwini

cia uzale

nia si

od funkcji szacuj

cej f(n)

Idea: funkcja szacuj

ca ocenia koszt osi

gni

cia celu

– wybiera si

zeł który jest najlepszy ( wg. funkcji szacuj

cj)

Implementacja: brzeg drzewa jest list

uporz

dkowan

malej

co według warto

ci funkcji szacuj

cej odległo

ść

Zasad

powy

realizuj

algorytmy:

malej

co według warto

ci funkcji szacuj

cej odległo

ść

celu.

• najpierw najlepszy „best-first”.
• najpierw najlepszy agresywny „greedy best-first”.

Zasad

powy

realizuj

algorytmy:

• najpierw najlepszy agresywny „greedy best-first”.
•

algorytm A*

© F.A. Dul 2007

4.1. Poszukiwania informowane

Poszukiwanie informowane

Zasada poszukiwania informowanego:

– wybór w

zła do rozwini

cia uzale

nia si

od funkcji szacuj

cej f(n)

Idea: funkcja szacuj

ca ocenia koszt osi

gni

cia celu

Idea: funkcja szacuj

ca ocenia koszt osi

gni

cia celu

– wybiera si

zeł który jest najlepszy ( wg. funkcji szacuj

cj)

Implementacja: brzeg drzewa jest list

uporz

dkowan

Zasad

powy

realizuj

algorytmy:

Implementacja: brzeg drzewa jest list

uporz

dkowan

malej

co według warto

ci funkcji szacuj

cej f(n).

• najpierw najlepszy „best-first”.
• agresywny najpierw najlepszy „greedy best-first”.

Zasad

powy

realizuj

algorytmy:

• algorytm A*

Funkcje szacuj

ce definiuje si

zwykle w oparciu

o odpowiedni

heurez

o odpowiedni

heurez

© F.A. Dul 2007

Algorytm „greedy best-first”

4.1. Poszukiwania informowane

Algorytm agresywny “najpierw najlepszy” (greedy best-first)

- rozwija si

zeł który le

y najbli

ej celu.

Funkcja szacuj

f(n) = h(n)

(

eurystyczna)

h(n) - oszacowanie kosztu z n do celu.

Funkcja h(n) nie jest cz

ęś

oryginalnego sformułowania

Funkcja h(n) nie jest cz

ęś

oryginalnego sformułowania

zadania!

Funkcja h(n) musi by

okre

lona na podstawie informacji

Funkcja h(n) musi by

okre

lona na podstawie informacji

dodatkowych; najcz

ęś

ciej heurystycznych.

© F.A. Dul 2007

4.1. Poszukiwania informowane

Własno

ci algorytmu „greedy best-first”

• Zupełno

ść

Nie, mog

powsta

zap

tlenia,

np. Iasi

Neamt

Iasi

Neamt ...

• Czas

O(b

), ale dobra heurystyka mo

• Czas

O(b

), ale dobra heurystyka mo

go znacznie zmniejszy

• Pami

ęć

O(b

) (przechowywanie wszystkich

• Pami

ęć

O(b

) (przechowywanie wszystkich

złów w pami

ci)

• Optymalno

ść

Nie

• Optymalno

ść

Nie

© F.A. Dul 2007

4.1. Poszukiwania informowane

Algorytm A* (A-star)

Najlepsza wersja algorytmu najpierw najlepszy (best-first)

Idea: nie rozwija

cie

ki, która ju

jest najkosztowniejsza.

Funkcja szacuj

f(n) = g(n) + h(n)

g(n) - koszt

cie

ki od startu do osi

gni

cia n,

h(n) - oszacowanie kosztu od n do osi

gni

cia celu,

h(n) - oszacowanie kosztu od n do osi

gni

cia celu,

f(n) - oszacowanie koszt

cie

ki od startu przez n do

osi

gni

cia celu.

A* u

ywa dopuszczalnej heurystyki do oszacowania h(n)

A* u

ywa dopuszczalnej heurystyki do oszacowania h(n)

Heurystyka jest dopuszczalna, je

eli nigdy nie przeszacowuje

kosztu osi

gni

cia celu, tzn. gdy jest optymistyczna.

kosztu osi

gni

cia celu, tzn. gdy jest optymistyczna.

Przykład: h(n) nigdy nie jest wi

ksza od odległo

ci drogowej

z n do celu.

© F.A. Dul 2007

z n do celu.

4.2. Heurystyki

Funkcje szacuj

ce definiuje si

zwykle w oparciu o heurez

[heureza] “reguła kciuka”, uproszczenie, odgadni

cie

[heureza] “reguła kciuka”, uproszczenie, odgadni

cie

prawidłowo

ci redukuj

ce koszt rozwi

zania problemu

w przypadkach, gdy jest on trudny lub niezrozumiały...

Algorytm A* u

ywa dopuszczalnej heurystyki do utworzenia

funkcji h(n).

UWAGA! W dalszej cz

ęś

ci b

dziemy uto

samia

poj

cia

heurystyki oraz funkcji h(n) mówi

c: “...heurystyka h(n)”

Heurystyka jest dopuszczalna, je

eli nigdy nie przeszacowuje

kosztu osi

gni

cia celu,tj.:

heurystyki oraz funkcji h(n) mówi

c: “...heurystyka h(n)”

kosztu osi

gni

cia celu,tj.:

1. h(n)

≤

h*(n), h*(n) - rzeczywisty koszt osi

gni

cia celu z n,

2. h(n)

≥

0, zatem h(G) = 0 dla ka

dego celu G.

© F.A. Dul 2007

2. h(n)

≥

0, zatem h(G) = 0 dla ka

dego celu G.

Heurystyka dopuszczalna jest zatem optymistyczna.

4.2. Heurystyki

Heurystyka dopuszczalna

Twierdzenie Je

eli h(n) jest okre

lona w oparciu o heurystyk

dopuszczaln

, to algorytm A* u

ywaj

cy algorytmu

TREE-SEARCH

jest optymalny.

Załó

my,

e na brzegu istnieje cel suboptymalny G

TREE-SEARCH

jest optymalny.

Dowód

Załó

my,

e na brzegu istnieje cel suboptymalny G

Niech n b

dzie nierozwini

tym w

złem

brzegu le

żą

cym na najkrótszej drodze

do celu optymalnego G.

f(G

) = g(G

) gdy

h(G

) = 0;

g(G ) > g(G) bo G jest

do celu optymalnego G.

g(G

) > g(G) bo G

jest

suboptymalny;

f(G) = g(G)

bo h(G) = 0

⇒

f(G

) > f(G);

f(G) = g(G)

bo h(G) = 0

⇒

f(G

) > f(G);

h(n)

≤

h*(n)

gdy

h jest dopuszczalna;

g(n) + h(n)

≤

g(n) + h

(n)

⇒

f(n)

≤

f(G);

© F.A. Dul 2007

Zatem f(G

) > f(n) i algorytm A

nigdy nie rozwinie w

zła G

c.b.d.o.

Heurystyka zgodna

4.2. Heurystyki

Heurystyka h(n) jest zgodna je

eli dla

dego w

zła n ka

dy nast

pnik n’

generowany przez działanie a spełnia

h(n)

≤

c(n,a,n’) + h(n’)

gdzie c(n,a,n’) jest kosztem działania a

eli heurystyka h(n) jest zgodna, to:

gdzie c(n,a,n’) jest kosztem działania a
dla w

złów n i n’.

f(n') = g(n') + h(n')

= g(n) + c(n,a,n') + h(n')

eli heurystyka h(n) jest zgodna, to:

= g(n) + c(n,a,n') + h(n')

≥

g(n) + h(n)

= f(n),

tj. f(n) jest funkcj

niemalej

wzdłu

dej

cie

ki.

Twierdzenie Je

eli h(n) jest zgodna, to algorytm A*

ywaj

cy algorytmu

GRAPH-SEARCH

jest optymalny.

tj. f(n) jest funkcj

niemalej

wzdłu

dej

cie

ki.

© F.A. Dul 2007

Twierdzenie Je

eli h(n) jest zgodna, to algorytm A*

ywaj

cy algorytmu

GRAPH-SEARCH

jest optymalny.

Optymalno

ść

algorytmu A*

4.2. Heurystyki

Algorytm A* rozwija w

zły wzgl

dem rosn

cych warto

ci f(n)

dodaj

c kolejno “f-kontury” w

złów.

Kontur i zawiera wszystkie w

zły dla których f = f

© F.A. Dul 2007

Kontur i zawiera wszystkie w

zły dla których f = f

przy czym f

< f

i+1

Własno

ci algorytmu A*

4.2. Heurystyki

• Zupełno

ść

Tak, chyba

e istnieje niesko

czenie wiele

celów o tym samym koszcie.

• Czas

Wykładniczy

• Czas

Wykładniczy

• Pami

ęć

Wykładniczy (przechowywanie
wszystkich w

złów w pami

ci)

wszystkich w

złów w pami

ci)

• Optymalno

ść

Tak

Najwi

kszym problemem algorytmu A* jest pami

ęć

Najwi

kszym problemem algorytmu A* jest pami

ęć

Modyfikacje A* pod k

tem ograniczenia pami

ci (zachowuj

zupełno

ść

i optymalno

ść

zupełno

ść

i optymalno

ść

• iteracyjnie pogł

biany A* (IDA*),

– rozwijanie zatrzymywane jest po przekroczeniu kosztu f = g + h

• rekursyjny najpierw najlepszy „recursive best-first”

– rekursywne utrzymywanie pami

ci na poziomie liniowym

• algorytm A* z ograniczon

pami

© F.A. Dul 2007

• algorytm A* z ograniczon

pami

– najdro

sze rozwini

cia s

odrzucane gdy brakuje pami

Heurystyki zgodne

Przykład - gra w osiem puzzli

4.2. Heurystyki

Przykład - gra w osiem puzzli

Przykładowe heurystyki:

• h

(n) = liczba

le ustawionych kostek,

• h (n) = całkowita odległo

ść

manhatta

ska (tj. liczba

• h

(n) = całkowita odległo

ść

manhatta

ska (tj. liczba

przesuni

ęć

z pozycji docelowej dla ka

dej kostki)

Dla pocz

tkowej konfiguracji kostek (S) mamy:

• h

(S) = 8 (wszystkie kostki s

le ustawione),

• h

(S) = 3+1+2+2+2+3+3+2 = 18

(przesuni

cia liczone bez uwzgl

dnienia

Dla pocz

tkowej konfiguracji kostek (S) mamy:

© F.A. Dul 2007

(przesuni

cia liczone bez uwzgl

dnienia

blokowania przez inne kostki)

Heurystyki dominuj

4.2. Heurystyki

eli dwie heurystyki dopuszczalne, h

(n) i h

(n) spełniaj

zale

ść

h (n)

≥

h (n)

dla ka

dego w

zła n,

(n)

≥

(n)

dla ka

dego w

zła n,

to heurystyka h

dominuje nad h

Heurystyka dominuj

ca jest lepsza przy poszukiwaniach.

Heurystyka dominuj

ca jest lepsza przy poszukiwaniach.

© F.A. Dul 2007

Jak wymy

dobr

heurystyk

dopuszczaln

4.2. Heurystyki

Nie ma ogólnych i zarazem skutecznych reguł wymy

lania

dobrych heurystyk dla szerokiej klasy zagadnie

na jednak poda

kilka wskazówek ułatwiaj

cych

Czasami heurystyka dopuszczalna mo

e by

uzyskana

na jednak poda

kilka wskazówek ułatwiaj

cych

tworzenie heurystyk.

Czasami heurystyka dopuszczalna mo

e by

uzyskana

poprzez rozlu

nienie organicze

zadania wyj

ciowego.

Koszt rozwi

zania zadania rozlu

nionego jest nie wi

kszy

Koszt rozwi

zania zadania rozlu

nionego jest nie wi

kszy

koszt rozwi

zania zadania wyj

ciowego.

Przykłady dla gry w osiem puzzli:

• je

eli kostki mogły by porusza

w dowolny sposób,

to h

(n) okre

la najta

sze rozwi

zanie;

to h

(n) okre

la najta

sze rozwi

zanie;

• je

eli kostki mogły by przemieszcza

do pól

siednich nawet gdy s

one zaj

te, to h

(n) okre

najta

sze rozwi

zanie.

© F.A. Dul 2007

najta

sze rozwi

zanie.

Jak wymy

dobr

heurystyk

dopuszczaln

4.2. Heurystyki

Czasami dobr

heurystyk

dopuszczaln

na uzyska

analizuj

c podproblemy zadania wyj

ciowego.

Dla gry w osiem puzzli mo

e to polega

na utworzeniu bazy

Dla gry w osiem puzzli mo

e to polega

na utworzeniu bazy

wzorców wszystkich rozwi

dla podzbiorów puzzli, np.:

Heurystyka dla konkretnego zadania jest tworzona z tych
wzorców.

wzorców.

Jeszcze innym sposobem jest tworzenie heurystyki na
podstawie zebranych do

wiadcze

i zastosowanie

© F.A. Dul 2007

podstawie zebranych do

wiadcze

i zastosowanie

algorytmu ucz

cego.

4.3. Algorytmy poszukiwa

lokalnych

Istnieje klasa zada

, w których droga doj

cia do celu nie jest

istotna - cel jest jednocze

nie rozwi

zaniem.

Przykład: rozmieszczenie na szachownicy o

miu królowych

Przykład: rozmieszczenie na szachownicy o

miu królowych

w taki sposób, aby wzajemnie si

nie atakowały.

Zadania takie mo

na rozwi

zywa

Zadania takie mo

na rozwi

zywa

przy pomocy algorytmów poszukiwa

lokalnych.
Stan - rozmieszczenie na szachownicy
o

miu królowych w dowolny sposób.

Poszukiwania lokalne polegaj

kolejnych zmianach stanu na takie,
które s

“lepsze”.

Po wykonaniu sekwencji zmian stanu
powinni

my uzyska

stan docelowy

które s

“lepsze”.

© F.A. Dul 2007

powinni

my uzyska

stan docelowy

(tu: jeden ze zbioru stanów docelowych).

Cechy algorytmów poszukiwa

lokalnych:

4.3. Algorytmy poszukiwa

lokalnych

Cechy algorytmów poszukiwa

lokalnych:

• nie potrzebuj

wielkiej pami

ci;

• pozwalaj

rozwi

zywa

zadania o bardzo du

wymiarze stanu.

Algorytmy poszukiwa

lokalnych s

blisko zwi

zane z

algorytmami optymalizacji.

Do algorytmów poszukiwa

lokalnych zalicza si

• algorytm „hill-climbing”
• algorytm symulowanego wy

arzania

• algorytm „local beam”
• algorytmy genetyczne

© F.A. Dul 2007

4.3. Algorytmy poszukiwa

lokalnych

Algorytm najszybszego wzrostu „hill-climbing”

Idea: zmiana stanu musi najlepiej poprawi

jako

ść

stanu.

Algorytm zachowuje si

“...jak cierpi

cy na amnezj

alpinista

Algorytm zachowuje si

“...jak cierpi

cy na amnezj

alpinista

wspinaj

cy si

w g

stej mgle na Mount Everest”.

function HILL-CLIMBING( problem) return a state that is a local maximum

input: problem, a problem
local variables: current, a node.

neighbor, a node.

current

←

MAKE-NODE(INITIAL-STATE[problem])

loop do

←

neighbor

←

a highest valued successor of current

if VALUE [neighbor]

≤

VALUE[current] then return STATE[current]

current

←

neighbor

current

←

neighbor

Zmiany stanu s

dobierane tak,

e warto

ść

funkcji celu

nie a

do osi

gni

cia najwi

kszej warto

ci w pobli

© F.A. Dul 2007

nie a

do osi

gni

cia najwi

kszej warto

ci w pobli

stanu startowego.

Algorytm najszybszego wzrostu „hill-climbing”

Problem: w zale

ci od stanu pocz

tkowego algorytm

4.3. Algorytmy poszukiwa

lokalnych

Problem: w zale

ci od stanu pocz

tkowego algorytm

e znajdywa

maksima lokalne funkcji celu.

• wersja stochastyczna - losowy wybór pomi

dzy kierunkami

wspinaczki,

© F.A. Dul 2007

wspinaczki,

• restart losowy w celu unikni

cia maksimum lokalnego.

Przykład - zadanie o

miu królowych na szachownicy

Nast

pnik - przestawienie pojedynczej królowej na inne pole

4.3. Algorytmy poszukiwa

lokalnych

Nast

pnik - przestawienie pojedynczej królowej na inne pole

w tej samej kolumnie szachownicy.

Heurystyka h(n): liczba par królowych które atakuj

wzajemnie (bezpo

rednio lub po

rednio).

Stan dla którego h(n) = 17
oraz stany nast

pne dla

których h(n) przyjmuj

Minimum lokalne h(n) = 1

© F.A. Dul 2007

których h(n) przyjmuj

warto

ci mniejsze.

Algorytm symulowanego wy

arzania

Idea: dopuszczenie “złych” zmian stanu w celu omini

cia

4.3. Algorytmy poszukiwa

lokalnych

Idea: dopuszczenie “złych” zmian stanu w celu omini

cia

maksimów lokalnych.
Złe zmiany stanu musz

coraz mniejsze i zachodzi

Złe zmiany stanu musz

coraz mniejsze i zachodzi

coraz rzadziej.
Pomysł zaczerpni

ty z …metalurgii. Opiera si

na technice

arzania metalu.

Co jaki

czas dopuszcza si

zmian

stanu na taki, któremu

odpowiada mniejsza warto

ść

funkcji celu.

odpowiada mniejsza warto

ść

funkcji celu.

Pozwala to “przeskoczy

na nast

pny pagórek” i w ten

sposób unikn

ąć

minimum lokalnego.

eli symulowana temperatura maleje dostatecznie wolno,

to algorytm symulowanego wy

arzania znajduje maksimum

globalne z prawdopodobie

stwem d

ążą

cym do jedno

ci.

sposób unikn

ąć

minimum lokalnego.

globalne z prawdopodobie

stwem d

ążą

cym do jedno

ci.

Metoda ta stosowana jest szerorko przy opracowywaniu
topologii układów VLSI, planowaniu rozkłdu lotów, itp.

topologii układów VLSI, planowaniu rozkłdu lotów, itp.

Algorytm symulowanego wy

arzania

4.3. Algorytmy poszukiwa

lokalnych

function SIMULATED-ANNEALING( problem, schedule) return a solution state

input: problem, a problem

schedule, a mapping from time to temperature

local variables: current, a node.

next, a node.
T, a “temperature” controlling the probability of

downward steps

current

←

MAKE-NODE(INITIAL-STATE[problem])

for t

←

1 to

∞

for t

←

1 to

∞

←

schedule[t]

if T = 0 then return current
next

←

a randomly selected successor of current

next

←

a randomly selected successor of current

∆

←

VALUE[next] - VALUE[current]

∆

E > 0 then current

←

next

else current

←

next only with probability e

∆

E /T

else current

←

next only with probability e

∆

E /T

Algorytm poszukiwania wi

„local beam”

Idea: operowanie na zbiorze k stanów zamiast na

4.3. Algorytmy poszukiwa

lokalnych

Idea: operowanie na zbiorze k stanów zamiast na
pojedynczym stanie.

• Przy starcie generuje si

losowo k stanów;

• Przy starcie generuje si

losowo k stanów;

• w ka

dym kroku wyznacza si

rozwini

cia wszystkich

stanów;

• je

eli jaki

nast

pnik osi

ł cel, to KONIEC;

• w przeciwnym razie wybiera si

k najlepszych stanów

• w przeciwnym razie wybiera si

k najlepszych stanów

i kontynuuje poszukiwania;

Zaleta: informacja propaguje si

na k w

tków obliczeniowych,

Zaleta: informacja propaguje si

na k w

tków obliczeniowych,

co poprawia zbie

ść

algorytmu.

Algorytmy genetyczne

4.3. Algorytmy poszukiwa

lokalnych

Idea: na

ladowanie natury poprzez dobór naturalny najlepiej

przystosowanych “osobników”.

• Algorytm operuje na zbiorze k stanów (

populacji

• Stan jest reprezentowany przez ła

cuch (

gen

) utworzony

z liter alfabetu sko

czonego (cz

sto alfabet jest binarny:

z liter alfabetu sko

czonego (cz

sto alfabet jest binarny:

0 i 1)

• Funkcja szacuj

ca (

funkcja dopasowania

). Wi

ksze

warto

ci odpowiadaj

lepszym stanom - “lepiej

warto

ci odpowiadaj

lepszym stanom - “lepiej

dostosowanym”.

• Start ze zbiorem k stanów wygenerowanych losowo.

• Start ze zbiorem k stanów wygenerowanych losowo.
• Stan potomny jest generowany przez kombinacj

dwóch

stanów rodzicielskich.

• Nowa generacja stanów uzyskiwana jest za pomoc

Algorytm genetyczny to algorytm wi

zkowy z rekombinacj

• Nowa generacja stanów uzyskiwana jest za pomoc

selekcji, krzy

owania i mutacji.

Algorytm genetyczny to algorytm wi

zkowy z rekombinacj

genetyczn

Algorytmy genetyczne

4.3. Algorytmy poszukiwa

lokalnych

Przykład dla zadania o

miu królowych na szachownicy

•

Funkcja dopasowania: liczba nieatakuj

cych si

par królowych

(min. = 0, max = 8

7/2 = 28)

(min. = 0, max = 8

7/2 = 28)

•

24/(24+23+20+11) = 31%

•

23/(24+23+20+11) = 29% etc.

Populacja Funkcja Selekcja Krzy

owanie Mutacje

Populacja Funkcja Selekcja Krzy

owanie Mutacje

pocz

tkowa dopasowania

Algorytmy genetyczne

4.3. Algorytmy poszukiwa

lokalnych

function GENETIC_ALGORITHM( population, FITNESS-FN) return an individual

input: population, a set of individuals

FITNESS-FN, a function which determines the quality of the individual

repeat

new_population

←

empty set

loop for i from 1 to SIZE(population) do

←

RANDOM_SELECTION(population, FITNESS_FN)

←

RANDOM_SELECTION(population, FITNESS_FN)

child

←

REPRODUCE(x,y)

child

←

REPRODUCE(x,y)

if (small random probability) then child

←

MUTATE(child )

add child to new_population

population

←

new_population

population

←

new_population

until some individual is fit enough or enough time has elapsed
return the best individual

4.5 Zadania eksploracji

Zadania rozpatrywane dotychczas mogły by

rozwi

zywane

offline, czyli przed podj

ciem działa

agenta.

Czasami zadania mysz

rozw

zywane online, czyli

• Poszukiwanie online jest niezb

dne w przypadku, gdy

Czasami zadania mysz

rozw

zywane online, czyli

naprzemian z obserwacjami i działaniami agenta.

• Poszukiwanie online jest niezb

dne w przypadku, gdy

rodowisko jest dynamiczne lub semi-dynamiczne,

gdy

nie ma mo

liwo

ci uwzgl

dnienia wszystkich

gdy

nie ma mo

liwo

ci uwzgl

dnienia wszystkich

sytuacji nieprzewidywalnych;

• Poszukiwanie online jest niezb

dne równie

przypadku zada

eksploracji, gdy

rodowisko jest

przypadku zada

eksploracji, gdy

rodowisko jest

nieznane a priori, np.:

– próbnik (łazik) planetarny,

– próbnik (łazik) planetarny,
– automatyczny zwiadowca,
– nowo narodzone dziecko...

Podsumowanie

• Algorytm „najlepszy-najpierw” jest algorytmem typu G

RAPH-

• Algorytm „najlepszy-najpierw” jest algorytmem typu G

RAPH-

EARCH

który rozwija w

zeł o najmniejszej warto

ci kosztu

wykorzystuj

c heurystyk

h(n), która szacuje koszt

poszukiwa

od w

zła n do celu.

poszukiwa

od w

zła n do celu.

• Algorytm agresywny „najlepszy-najpierw” rozwija w

zły

z najmniejsz

warto

h(n). Nie jest optymalny, ale czasem

z najmniejsz

warto

h(n). Nie jest optymalny, ale czasem

efektywny.

• Algorytm A* rozwija w

zły z najmniejsz

warto

f(n) = g(n) + h(n). Algorytm A* jest zupełny i optymalny

f(n) = g(n) + h(n). Algorytm A* jest zupełny i optymalny
je

eli h(n) jest dopuszczalna (dla T

REE-

EARCH

)

lub zgodna (dla G

RAPH-

EARCH

• Efektywno

ść

algorytmów informowanych zale

y od jako

heurystyk.

• Dobra heurystyka mo

e by

sto uzyskana poprzez

• Dobra heurystyka mo

e by

sto uzyskana poprzez

rozlu

nienie ogranicze

zadania.

Podsumowanie

• Metody poszukiwa

lokalnych (np. hill climbing) wykorzystuj

• Metody poszukiwa

lokalnych (np. hill climbing) wykorzystuj

tylko pojedyncze stany, nie wymagaj

c du

ej pami

ci.

• Algorytm stochastyczny symulowanego wy

arzania polega

• Algorytm stochastyczny symulowanego wy

arzania polega

na losowym generowaniu kierunków poszukiwa

o malej

cych amplitudach.

Pozwala wyznacza

efektywnie rozwi

zanie globalne

Pozwala wyznacza

efektywnie rozwi

zanie globalne

„uciekaj

c” z minimów lokalnych.

• Algorytmy genetyczne s

stochastyczn

wersj

algorytmów

hill-climbing które do wyznaczania kierunków poszukiwa

ywaj

mechanizmów genetycznych: krzy

owania, mutacji

i selekcji.

• Zadania eksploracji, w których agent nie ma wiedzy

rodowisku, mog

rozwi

zywane metodami

poszukiwa

bie

żą

cych (online search).

poszukiwa

bie

żą

cych (online search).

• W metodach online search agent tworzy map

rodowiska

na podstawie której znajduje cel, o ile on istnieje.

• Pomocne jest ulepszanie heurystyk na podstawie obserwacji

rodowiska.