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

• Autorzy: Gałuszka A. , Świerniak A.

Warianty tytułu

EN

Polynomial time complete optimal algorithm for "block world" problems

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

algorytmy zachłanne; świat klocków; system STRIPS; planowanie zadań; osiąganie celów

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2001
• Tom: z. 133
• Strony: 129--141
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Gałuszka A.

autor

Świerniak A.

• Instytut Automatyki Politechnika Śląska, 44-100 Gliwice, ul. Akademicka 16, tel. [phone],