Planowanie akcji
Planowanie akcji to zagadnienie związane ze sztuczną inteligencją, a tym samym z robotami. Celem planowania jest osiągnięcie przez robota jednego z docelowych stanów poprzez wykonanie elementarnych akcji (takich jak ruch do przodu, obrót, cofnięcie, itp). Najczęściej polega to na przeszukaniu określonego zestawu stanów (punktów) pośrednich i wybraniu takiej ścieżki, która poprowadzi robota od punktu początkowego do punktu końcowego.
Podczas planowania akcji brane jest pod uwagę to, jak długo wyznaczana będzie trasa (Złożoność obliczeniowa). Najczęściej dopuszcza się określenie trasy suboptymalnej, ponieważ gwarantuje ono dotarcie do celu, a także można je uzyskać w znacznie krótszym czasie. Jako przykład można podać zadanie, w którym optymalny zestaw elementarnych akcji wyznaczany jest w ciągu 20 lat; natomiast rozwiązanie suboptymalne zajmuje 10 minut i jest 5 razy gorsze od optymalnego.
Wśród metod przeszukiwania zestawu możliwych rozwiązań (w postaci drzewa lub grafu) wymienić można:
- przeszukiwanie wszerz - metoda ta polega na sprawdzeniu wszystkich możliwości ruchu robota z punktu startowego, następnie z osiągniętych punktów generuje się kolejne. Operacje powtarza się tak długo, aż znajdzie się rozwiązanie. Metoda ta gwarantuje znalezienie rozwiązania, ale może zająć bardzo dużo czasu.
- przeszukiwanie w głąb - w tej metodzie przeszukiwane są gałęzie do wybranego poziomu. Jeśli nie zostanie znalezione rozwiązanie, to brana jest inna gałąź. Metoda ta pozwala szybko wyznaczyć rozwiązanie, pod warunkiem że zadany poziom jest równy (lub niższy) poziomowi na którym znajduje się rozwiązanie. W przeciwnym wypadku nie znajdziemy rozwiązania.
- algorytm A* - metoda ta polega na skonstruowaniu funkcji przyjmującej wartość równą sumie odległości od punktu startowego oraz szacowanej odległości od punktu docelowego. Pozwala ona określić kierunek, w którym należy się poruszać. Im lepsze szacowanie, tym szybciej można znaleźć rozwiązanie.