Ideea fundamentala
Un nod poate reprezenta o pozitie, o stare sau o ipoteza. O muchie poate reprezenta o deplasare, o actiune sau o tranzitie. Drumul minim minimizeaza suma costurilor tranzitiilor.
Nu toate problemele AI sunt probleme de drum minim: modelarea prin graf si alegerea costurilor trebuie justificate.
Exemple de aplicatii
| Aplicatie | Noduri | Costul muchiilor | Obiectiv |
|---|---|---|---|
| Navigatia robotilor | Pozitii accesibile | Distanta, energie, risc | Traseul optim |
| Vehicule autonome | Stari de deplasare | Timp, risc, confort | Traiectoria optima |
| Jocuri video | Pozitii ale personajelor | Distanta, obstacole, pericole | Deplasarea NPC |
| Planificarea actiunilor | Stari ale sistemului | Costul unei actiuni | Secventa optima de actiuni |
| Recunoasterea vorbirii | Ipoteze de recunoastere | Costuri din probabilitati | Secventa cea mai probabila |
| Procesarea limbajului | Stari de analiza | Costuri ale interpretarilor | Analiza optima |
| Analiza imaginilor | Pixeli sau regiuni | Culoare, textura, pozitie | Contururi optime |
| Grafuri de cunostinte | Entitati si concepte | Relevanta sau incredere | Lant de relatii optim |
| Robotica industriala | Configuratii articulare | Energie, timp, risc | Miscari optime |
| Sisteme multiagent | Stari comune ale agentilor | Timp, energie, conflicte | Planuri coordonate |
Trei exemple dezvoltate
Navigatia robotului · Rezolvarea unui puzzle · Recunoasterea vorbirii