Wielomianowy algorytm generujący optymalny plan dla problemów z dziedziny "świata klocków"

W artykule rozważane są charakterystyczne dla Sztucznej Inteligencji problemy planowania zadań i osiągania celów. Rozważania dotyczące złożoności obliczeniowej umożliwiły zastosowanie strategii zachłannej do wyboru podcelu spośród podcelów wynikających z grafu ograniczeń kolejnościowych. Strategia zachłanna w przypadku dziedziny "świata klocków" prowadzi do znalezienia optymalnego (w sensie najmniejszej liczby operatorów rozwiązujących problem) planu. Przykład wyjaśnia istotę zachłanności wyborów w środowisku tzw. "świata klocków". We wszystkich przypadkach problem planowania zamodelowany został przy użyciu reprezentacji STRIPS.

---

In this paper planning and goal persuit problems in artificial intelligence are considered. The analysis of computational complexity allows to apply greedy strategy to choose subgoal which respect precedence constraints graph of the problem. In the case of "block world" environment the greedy strategy leads to finding optimal problem solution. The essence of this approach is explained by the example in block world environment. In all cases planning problems have been modelled using STRIPS representation.