inteligenta artificiala: strategii de cautare

Inteligenţă artificială

2. Strategii de căutare Florin Leon

Universitatea Tehnică „Gheorghe Asachi” din Iaşi

Facultatea de Automatică şi Calculatoare

http://florinleon.byethost24.com/curs_ia.htm

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

2

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

3

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

4

Probleme de căutare

15 puzzle Turnurile din Hanoi

Labirinturi 8 regine Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

5

Probleme de căutare reale

Planificare Găsirea rutelor

Programarea telescoapelor Navigarea roboţilor militari Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

6

Alte aplicaţii

Găsirea rutelor

Rezervarea biletelor pentru avioane, trenuri etc.

Reţele de calculatoare

Distribuţia coletelor poştale

Asemănătoare problemei comis-voiajorului

Proiectarea instalaţiilor, VLSI

Proiectarea cablurilor şi ţevilor într-o clădire, într-o maşină

Conectarea pinilor circuitelor electronice, cu scopul de a minimiza aria şi de a maximiza viteza prin minimizarea lungimii conexiunilor

Crearea medicamentelor

Găsirea substanţelor celor mai potrivite care permit substanţei active să se cupleze la zona dorită

Jocuri video

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

7

Componentele unei probleme de căutare

Starea iniţială

Starea scop

O mulţime de operatori

Funcţia de evaluare – pentru căutarea informată

Cât de departe este fiecare stare de starea scop

Conţine cunoştinţe despre fiecare problemă în parte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

8

Formalizarea unei probleme de căutare

Q este o mulţime finită de stări

S Q este o mulţime nevidă de stări iniţiale

G Q este o mulţime nevidă de stări scop

succs : Q (Q) reprezintă mulţimea de stări care pot fi atinse din starea s într-un singur pas

Funcţia primeşte o singură stare ca argument şi returnează o mulţime de stări ca rezultat

cost : Q2 R+ reprezintă costul de a ajunge din starea s în starea s’

Funcţia primeşte 2 stări şi returnează un număr pozitiv

cost(s,s’ ) este definită doar când s’ succs(s)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

9

Definiţii

Spaţiu de căutare (spaţiul problemei)

Mulţimea tuturor stărilor care pot fi atinse prin aplicarea operatorilor disponibili

Soluţie

Seria de operatori care transformă starea iniţială într-o stare scop

Metodă de rezolvare a unei probleme

O procedură pentru găsirea unei soluţii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

10

Rezolvarea unei probleme prin căutare

Stare

iniţială

Stare

scop

Spaţiul de căutare

(spaţiul problemei)

Soluţie

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

11

Soluţia

O soluţie este o cale care leagă nodul iniţial de oricare din nodurile scop

I

G

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

12

Soluţia

O soluţie este o cale care leagă nodul iniţial de oricare din nodurile scop

Costul căii este suma costurilor arcelor care formează calea

O soluţie optimă este soluţia de cost minim

Unele probleme nu au soluţie!

I

G

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

13

Existenţa soluţiei

12 14 11

15 10

13 9 5 6 7 8

4 3 2 1

12 15 11

14 10

13 9 5 6 7 8

4 3 2 1

?

1000 $

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

14

Dimensiunea spaţiului de căutare

8-puzzle 9! = 362.880 stări

15-puzzle 16! 2 · 1013 stări

24-puzzle 25! 1025 stări

Doar jumătate din aceste stări pot fi atinse dintr-o stare dată

Dar într-o abordare simplă acest lucru nu se cunoaşte dinainte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

15

Căutarea în spaţiul problemei

Deseori construirea unei reprezentări complete a grafului de căutare nu este fezabilă sau este prea costisitoare

Algoritmul de rezolvare trebuie să construiască soluţia prin explorarea unei porţiuni restrânse a grafului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

16

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

17

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

18

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

19

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

20

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

21

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

22

Reprezentarea

Care este spaţiul problemei?

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

23

Costul unui pas orizontal / vertical = 1 Costul unui pas diagonal = 2

Abordarea 1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

24

Soluţia optimă

Această cale este cea mai scurtă în spaţiul discretizat, dar nu şi în spaţiul iniţial continuu

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

25

Abordarea 2

Costul unui pas: lungimea segmentului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

26

Abordarea 2

Costul unui pas: lungimea segmentului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

27

Soluţia

Cea mai scurtă cale în acest spaţiu este cea mai scurtă şi în spaţiul iniţial

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

28

Misionarii şi canibalii

3 misionari, 3 canibali, 1 barcă

Barca poate duce 2 persoane

Dacă sunt mai mulţi canibali decât misionari, îi mănâncă

5 operatori: 1C, 1M, 2C, 2M, CM

Alternativă: persoanele individuale (27 de operatori)

Reprezentare: numărul de persoane pe primul mal şi barca

Starea iniţială: (3, 3, 1)

Starea scop: (0, 0, 0)

O reprezentare mai bună reduce spaţiul de căutare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

29

Presupuneri

Mediul este static

Mediul este discret (sau discretizabil)

Mediul este accesibil (observabil)

Mediul este determinist

Multe din aceste presupuneri pot fi înlăturate şi căutarea tot rămâne o metodă importantă de rezolvare a problemelor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

30

Noduri şi stări

Un nod este o structură de date în program

O stare este o configuraţie a problemei

Un nod are:

Stare

Nod părinte

Operatorul care a fost aplicat pentru a-l genera

Adâncime

Cost (al căii parcurse din starea iniţială)

Două noduri diferite pot conţine aceeaşi stare!

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

31

Frontiera arborelui de căutare

Frontiera (engl. fringe) este mulţimea tuturor nodurilor care nu au fost încă expandate

1

2 3 4 5 6

7 8

1

2 3 4 5 6

7 8

1

2 3 4 5 6

7 8

1 3 5 6

8

1 3

4

5 6 7

8 2 4 7

2

1

2 3 4 5 6

7 8

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

32

Strategia de căutare

Frontiera este implementată ca o listă

Ordonarea nodurilor în frontieră defineşte strategia de căutare

De exemplu tratarea listei ca o coadă sau ca o stivă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

33

Măsuri de performanţă

Completitudine

Un algoritm este complet dacă găseşte o soluţie atunci când există una

Dar dacă nu există o soluţie?

Optimalitate

Un algoritm este optim dacă returnează o soluţie de cost minim când problema are soluţii

Complexitate

Măsoară timpul şi volumul de memorie necesare algoritmului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

34

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

35

Căutarea neinformată

Raţionamentul constă în explorarea alternativelor

Căutarea în lăţime (engl. breadth-first search)

Căutarea bidirecţională

Căutarea în adâncime (engl. depth-first search)

Căutarea limitată în adâncime (engl. depth-limited search)

Căutarea iterativă în adâncime (engl. iterative deepening search)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

36

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei (lista e o coadă)

FRONTIERA = (1)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

37

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei

FRONTIERA = (2, 3)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

38

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei

FRONTIERA = (3, 4, 5)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

39

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei

FRONTIERA = (4, 5, 6, 7)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

40

Parametri importanţi

Numărul maxim de succesori ai oricărei stări

Factorul de ramificare (engl. branching factor) b al arborelui de căutare

Lungimea minimă (≠ cost) a căii între starea iniţială şi o stare scop

Adâncimea (engl. depth) d a celui mai superficial nod scop din arborele de căutare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

41

Evaluarea performanţelor

Căutarea în lăţime este:

Completă

Optimă dacă un pas are costul 1

Numărul de noduri generate (cazul cel mai defavorabil)

1 + b + b2 + … + bd = (bd+1-1)/(b-1) = O(bd)

Complexitatea de timp şi de spaţiu este O(bd)

Numărul de noduri generate (cazul cel mai favorabil)

1 + b + b2 + … + bd-1 + 1 = 1+(bd-1)/(b-1) = O(bd-1)

Nu este o diferenţă foarte mare, performanţele sunt destul de predictibile

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

42

Notă

Căutarea în lăţime poate rula la infinit dacă:

Problema nu are soluţii şi spaţiul de căutare este infinit

sau

Stările pot fi revizitate de mai multe ori

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

43

Căutarea bidirecţională

Două frontiere: FRONT1 şi FRONT2

Complexitatea de timp şi spaţiu este O(bd/2) O(bd) dacă ambii arbori au acelaşi factor de ramificare b

s

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

44

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei (lista e o stivă)

1

2 3

4 5

FRONTIERA = (1)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

45

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

FRONTIERA = (2, 3)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

46

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

FRONTIERA = (4, 5, 3)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

47

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

48

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

49

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

50

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

51

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

52

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

53

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

54

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

55

Evaluarea performanţelor

b: factorul de ramificare d: adâncimea celui mai superficial nod scop m: adâncimea arborelui de căutare Căutarea în adâncime:

Nu este completă Nu este optimă

Cazul cel mai favorabil Complexitatea de timp şi de spaţiu este O(d) – extrem de rapid

Cazul mediu Complexitatea de timp este similară cu a căutării în lăţime: O(bd) De obicei, DFS este mai rapid decât BFS

Cazul cel mai defavorabil Complexitatea de timp este O(bm) – căutarea este lentă Complexitatea de spaţiu este O(b ∙ m) – excelentă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

56

Căutarea limitată în adâncime

Căutare în adâncime cu limitarea la k niveluri

Sub această adâncime nodurile nu mai sunt expandate

Situaţii posibile:

Găsirea unei soluţii

Eşec (nu există soluţie)

Căutare incompletă (nu există soluţie pe nivelurile considerate)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

57

Căutarea iterativă în adâncime

Combină avantajele căutărilor în lăţime şi adâncime

Ideea de bază: pentru k = 0, 1, 2, …

Realizează căutare limitată în adâncime pentru limita k

Generează nodurile cu adâncime k

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

58

Căutarea iterativă în adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

59

Căutarea iterativă în adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

60

Căutarea iterativă în adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

61

Evaluarea performanţelor

Căutarea iterativă în adâncime este: Completă

Optimă dacă un pas are costul 1

Cazul cel mai defavorabil Complexitatea de timp:

(d+1) ∙ (1) + d ∙ b + (d-1) ∙ b2 + … + (1) ∙ bd = O(bd)

Comparabilă cu a căutării în lăţime, puţin mai lentă din cauza repetiţiilor

Complexitatea de spaţiu: O(b ∙ d) Comparabilă cu a căutării în adâncime, foarte bună

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

62

Compararea performanţelor

Trei probleme (în ordine crescătoare a complexităţii):

15-puzzle: b = 2,13

Cubul Rubik: b = 13,5

Şah: b = 35 (nu este o problemă de căutare de tipul celorlalte, e un joc, vezi cursul 3)

Timpul şi spaţiul de prelucrare

1 milion de noduri pe secundă

100 octeţi pe nod

Tabelele următoare prezintă cazurile cele mai defavorabile

Pentru analiza cazurilor celor mai favorabile:

tw: cel mai defavorabil, tb: cel mai favorabil

Căutare în lăţime (BFS), bidirecţională tw / tb b

Căutare iterativă în adâncime (IDS) tw / tb b/2

Căutare în adâncime (DFS) tw este exponenţial, tb este liniar

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

63

15-puzzle: b = 2,13

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

64

Cubul Rubik: b = 13,5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

65

Şah: b = 35

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

66

Evitarea repetării stărilor

Evitarea întoarcerii în starea din care tocmai s-a plecat

Starea fiului este identică cu starea părintelui

Evitarea căilor cu bucle

Starea unui nod este identică cu starea unui nod de pe calea din starea iniţială

Evitarea stărilor generate anterior

Necesită memorarea tuturor stărilor generate: complexitate de spaţiu posibil O(bd)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

67

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

68

Căutarea informată (euristică)

Factorii de ramificare mari sunt o problemă serioasă

Trebuie găsită o modalitate de a reduce numărul de noduri vizitate

Metodele de căutare euristică încearcă alegerea „inteligentă” a nodurilor care trebuie expandate

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

69

Euristică

εὑρίσκειν = a găsi, evrika = am găsit

O euristică este o metodă care furnizează rapid o soluţie, nu neapărat optimă

Este deci o metodă aproximativă, spre deosebire de un algoritm exact optim

Deşi nu garantează găsirea soluţiei optime, metodele euristice funcţionează de obicei (foarte) bine

Chiar dacă nu găsesc soluţia optimă, găsesc de cele mai multe ori o soluţie acceptabilă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

70

Strategii neinformate vs. Strategii informate

Strategiile neinformate (oarbe) Nu exploatează semnificaţiile stărilor pentru a ordona

nodurile din frontieră

Exploatează doar poziţiile nodurilor în arbore

Tratează toate problemele la fel

Strategiile informate (euristice) Ordonează nodurile frontierei în funcţie de semnificaţiile

stărilor

Cele mai „promiţătoare” noduri sunt plasate la începutul frontierei

Utilizează cunoştinţele specifice fiecărei probleme

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

71

Căutarea Best-First

Evaluează cât de bun este un nod

Utilizează o funcţie de evaluare f care atribuie fiecărui nod n un număr real f(n) 0

f(n) este un cost estimat

Cu cât este mai mic f(n), cu atât este mai bun nodul n

Căutarea Best-First sortează frontiera în ordinea crescătoare a lui f

Pentru f egale, se decide aleatoriu

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Definirea lui f

72

Funcţii utilizate în general g(n) este costul căii de la nodul iniţial la n

Este cunoscută

h(n) este estimarea costului căii de la n la un nod scop Este o estimare euristică

Căutarea de cost uniform (neinformată) f(n) = g(n)

Căutarea Greedy f(n) = h(n)

Căutarea A* f(n) = g(n) + h(n)

Reuneşte ideile căutărilor de cost uniform şi greedy

Problema principală: găsirea celei mai bune funcţii h

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

73

Calitatea căutării este dată de h

Când h = costul până la scop

Sunt expandate doar nodurile de pe calea corectă

Se găseşte soluţia optimă

Când h < costul până la scop

Sunt expandate noduri suplimentare

Se găseşte soluţia optimă

Când h > costul până la scop

Soluţia optimă poate fi trecută cu vederea

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

74

Exemplu: căutarea Greedy

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

75 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

76

Căutarea Greedy

Iaşi – Făgăraş: prin Piatra Neamţ

Dacă se permite revizitarea stărilor, buclă infinită

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

77

Performanţele căutării Greedy

Nu este optimă

Este incompletă dacă:

Nu se foloseşte o coadă de priorităţi iar succesorul cel mai promiţător este expandat direct

Aceasta este abordarea cea mai utilizată

Nodurile sunt adăugate la începutul cozii de priorităţi (~ căutare în adâncime) iar euristica este constantă (de exemplu euristica naivă: h = 0)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

78

Fie h*(n) costul căii optime de la n la un nod scop

Funcţia euristică h(n) este admisibilă dacă: 0 h(n) h*(n)

Dacă G este scop, atunci h(G) = 0

O funcţie euristică admisibilă este întotdeauna optimistă (niciodată nu supraestimează)

Euristici admisibile

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

79

Căutarea A*

Unul din cei mai populari algoritmi de IA

f(n) = g(n) + h(n), unde:

g(n) = costul celei mai bune căi găsite până la n

h(n) = o funcţie euristică admisibilă

Presupunem că: n, n’, : cost(n, n’) > 0

Între două noduri diferite există întotdeauna un cost pozitiv

Căile infinite au cost infinit

Foloseşte 2 liste: OPEN şi CLOSED

Mulţimea nodurilor din lista OPEN reprezintă frontiera, iar cele din lista CLOSED interiorul zonelor vizitate

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

80

Greedy şi A*

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

f(B) = 15 + 20 + 30 = 65

f(C) = 15 +10 + 35 = 60

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Algoritmul A*: pseudocod

81 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

82 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

83

Revizitarea stărilor

Euristica h este admisibilă

Într-o situaţie reală, nodul cu h = 1 ar putea fi lângă scop, dar despărţit de acesta de un obstacol

c = 1

100

2 1

2

h = 100

0

90

1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

84

Revizitarea stărilor

c = 1

100

2 1

2

h = 100

0

90

1

104

4+90

f = 1+100 2+1

?

Dacă eliminăm acest nod, algoritmul expandează nodul scop vecin şi returnează o soluţie sub-optimă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

85

1

100

2 1

2

100

0

90

1

104

4+90

1+100 2+1

2+90

102

Dacă nu eliminăm nodurile care revizitează stările, căutarea se termină cu soluţia optimă

Revizitarea stărilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

86

1

100

2 1

2

100

0

90

1

Noduri introduse, noduri scoase în/din coada de priorităţi

Cum funcţionează A*

B(101), C(3)

C(3), B(101) – sortată după f

B(101), D(94)

D(94), B(101) – sortată după f

B(101), E(104)

E(104), D(92)

D(92), E(104) – sortată după f

E(104), E(102)

E(102), E(104) – sortată după f

Scop: E(102)

A

B C

D

E

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

87

O euristică h este monotonă (sau consistentă) dacă:

n şi un fiu n’ al lui n:

h(n) cost(n, n’) + h(n’)

G un nod scop

h(G) = 0

O euristică monotonă este şi admisibilă

O euristică monotonă devine din ce în ce mai precisă cu cât înaintează în adâncimea arborelui de căutare

Euristici monotone

(inegalitatea în triunghi)

n

n’ h(n)

h(n’)

cost(n,n’)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

88

Euristici monotone

Dacă h este monotonă, oricând este deschis un nod, algoritmul A* garantează că a găsit o cale optimă către acesta

Nodurile închise nu mai sunt redeschise

În multe cazuri (dar nu întotdeauna), monotonia euristicii accelerează găsirea soluţiei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Ecuaţia pathmax

Ecuaţia pathmax: la generarea unui nod fiu n’ al lui n

f(n’) = max( f(n), g(n’) + h(n’) )

În exemplul anterior: nodul D

f(D) = max( f(B), g(D) + h(D) ) = max( 101, 92 ) = 101

Ecuaţia pathmax face ca valorile lui f să fie monoton nedescrescătoare pe orice cale din arborele de căutare

Ecuaţia pathmax nu transformă o funcţie de cost f nemonotonă într-una monotonă

Dacă există mai multe căi prin care se poate ajunge la scop, valorile f pot rămâne nemonotone pentru căile netraversate încă

89 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

90

Caracteristici ale A*

A* este complet şi optim

Dacă nodurile care revizitează stările nu sunt eliminate

A* este eficient optim (engl. “optimally efficient”)

Niciun alt algoritm de acelaşi tip nu garantează expandarea unui număr mai mic de noduri

Este eficient optim doar dacă euristica este monotonă

Alţi algoritmi pot fi mai rapizi chiar dacă expandează mai multe noduri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

91

Complexitatea A*

Timp

Calitatea euristicii h scade timpul necesar

Cazul cel mai favorabil: h este perfectă, O(d)

Cazul cel mai defavorabil: h = 0, O(bd) ~ BFS

Spaţiu

Toate nodurile sunt memorate

Cazul cel mai defavorabil: O(nS)

nS este numărul de stări

A* are în general probleme de spaţiu înainte de a avea probleme de timp

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Cazul cel mai defavorabil

Exemplu de caz cel mai defavorabil pentru A* cu euristici inconsistente: familia Martelli – G5

O(2n) expandări de noduri pentru găsirea soluţiei

92 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Optimizări

Optimizarea listelor

Căutarea celui mai bun nod, de fiecare dată, este ineficientă

Lista deschisă trebuie să fie o listă sortată sau un arbore heap

Lista închisă poate fi un hashtable

Optimizarea spaţiului de căutare

Cel mai simplu caz: “parent pruning” – evitarea expandării ca succesor a părintelui unui nod

93 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

94

Optimizări

Aplicarea pe grid, de exemplu pentru jocuri, este costisitoare

Există foarte multe stări dacă gridul este mare

Factor de ramificare mare: 4, 8 sau 6 pentru grid hexagonal

Multe căi au aceeaşi lungime. A* le poate explora pe toate

Se poate ajusta valoarea h în mod determinist, de exemplu se poate creşte cu 0,1%. A* va prefera expandarea nodurilor mai apropiate de scop

În general: h *= (1 + p), cu p < (costul minim al unui pas) / (lungimea aşteptată a celei mai lungi căi)

Alternativă: când valorile f sunt egale, se compară după valorile h

h poate fi mărită puţin, devenind neadmisibilă. Dacă funcţia rezultată h’ supraestimează rareori funcţia h* cu o valoare mai mare decât v, atunci algoritmul va găsi rareori o soluţie al cărei cost este mai mare cu v decât costul optim

Altă metodă pentru departajare: se preferă căile apropiate de linia dreaptă între starea iniţială şi scop

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Optimizări

A* ierarhic cvasi-optim (Near-Optimal Hierarchical Pathfinding, HPA*)

95 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

96

IDA*

Căutarea iterativă în adâncime A* (engl. Iterative Deepening A*)

Principiu similar cu acela al căutării iterative neinformate în adâncime

În loc de niveluri în arbore foloseşte contururi de cost ale funcţiei f

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

97

Algoritmul IDA*: pseudocod

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Ecuaţia pathmax bidirecţională

Actualizarea dinspre părinţi spre fii

h(c) = max( h(c), h(p) – cost(p,c ) )

Actualizarea dinspre fii spre părinţi

h(p) = max( h(p), h(c) – cost(c, p) )

Regula poate elimina multe noduri care altfel ar fi generate şi chiar expandate (idee asemănătoare cu retezarea alfa-beta pentru jocuri, din cursul 3)

98 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Exemplu

Să presupunem că pragul curent al IDA* este T = 2

Fără aplicarea regulii, atât parintele p şi fiul c2 sunt expandaţi f(p) = 0 + 2 = 2

f(c2) = 1 + 1 = 2

Cu regula BPMX: f(c1) = 1 + 5 = 6, IDA* îl va ignora

Se va actualiza h(p) = 4 şi deci f(p) = 0 + 4 = 4

IDA* va ignora nodul p şi nu va mai genera nodul c2

99 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

100

Crearea de euristici

O euristică admisibilă poate fi văzută drept costul soluţiei optime a unei probleme relaxate (prin eliminarea constrângerilor)

Pentru navigarea unui robot:

Distanţa Manhattan corespunde eliminării obstacolelor

Distanţa euclidiană corespunde eliminării obstacolelor şi a constrângerilor de mişcare pe grid

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Euristici pentru 8-puzzle (I)

101

Numărul de căsuţe diferite (fără a include spaţiul)

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

N N N

N N N

N D

Doar “8” este plasat diferit, deci funcţia euristică este evaluată la 1 Euristica ne spune că o soluţie ar putea fi găsită într-o mutare

Starea scop

Starea curentă

h(scrt) = 1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Euristici pentru 8-puzzle (II)

102

Distanţa Manhattan (fără a include spaţiul)

Doar căsuţele “3”, “8” şi “1” sunt plasate greşit, deci funcţia euristică întoarce 8 Euristica ne spune că o soluţie ar putea fi găsită în cel puţin 8 mutări

3 2 8

4 5 6

7 1

1 2 3

4 5 6

7 8

Starea scop

Starea curentă

3 3

8

8

1

1

2 spaţii

3 spaţii

3 spaţii

Total 8 h(scrt) = 8

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

103

Modalităţi suplimentare de alegere a funcţiei euristice

Abordarea maximă

h(n) = max( h1(n), …, hm(n) )

Abordarea statistică

De exemplu, dacă în 90% din cazuri când h(n) = 14, h*(n) = 18, atunci când valoarea lui h(n) este 14, returnăm 18

Complexitatea euristicii nu trebuie să afecteze eficienţa căutării

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

104

IDS vs. A*

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

105

Concluzii

Metodele de căutare sunt utile când:

Spaţiul de căutare este mic şi

Nu există alte tehnici disponibile sau

Dezvoltarea unei tehnici mai eficiente nu merită efortul

Spaţiul de căutare este mare şi

Nu există alte tehnici disponibile şi

Există euristici „bune” pentru problema considerată

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm