Wyniki wyszukiwania - BazTech

1

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

Gałuszka A., Świerniak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2001

|

z. 133

129-141

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.

2

Zachłanny algorytm planowania w 'świecie klocków'.

Gałuszka A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 125

261-267

PL

Niniejszy artykuł analizuje zadania ze 'świata klocków', w których sytuację docelową stanowi opis wielu wież klocków. W ogólnym przypadku generacja optymalnego planu rozwiązującego takie zadanie jest problemem NP złożonym. Graf ograniczeń kolejnościowych redukuje przestrzeń stanów zadania. Artykuł pokazuje jak taki graf można zbudowć. Graf ten umożliwia zaimplementowanie algorytmu zachłannego, który generuje rozwiązanie. Algorytm ten jest wielmianowo złożony w czasie. Omówione zostały także warunki konieczne i wystarczające optymalności algorytmu zachłannego.

EN

In this paper block world instance where the goal state is a complete description of a set of stacks is presented. In general to generate an optimal plan for such problem is NP-hard. Precedence constraints graph reduces block world states space. It is shown how this graph this graph can be built. Now it is possible to implement greedy algorithm which generates solution. This algorithms is polynomial-time complete. Necessary and sufficient of greedy algorithm optimality are also discussed.

3

Rozwiązywanie zadań ze świata klocków

Gałuszka A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 122

15-27

PL

Świat Klocków jest wygodną reprezentacją dla problemów planowania. Istnieje wiele różnych algorytmów, które używają reprezentacji zadania typu STRIPS przy rozwiązywaniu zadań ze Świata Klocków. Niektóre z nich przy poszukiwaniu rozwiązania przeszukują przestrzeń stanów świata, inne przestrzeń stanów planu. W artykule prezentowana jest rozszerzona hierarchia podcelów oraz różne dziedziny operatorów. Nietóre z podcelów są trudne do rozwiązania dla wszystkich algorytmów. Główną częścia pracy jest propozycja innego podejścia do przeszukiwania przestrzeni stanów. Proponowany algorytm znajduje rozwiązanie zadania poprzez przeszukiwanie jednej ścieżki w grafie przestrzeni stanów dla wszystkich typów podcelów. Ceną szybkości algorytmu jest suboptymalność rozwiązania. Przykłady wyjaśniają propozycję innego podejścia.

EN

Block world is a cconvenient representation for planning problems. There are many different algorithms of state space searching which use STRIPS representation for planning. Some of them search for solution through a space of world states, some of them trhough a space of plan-states. In the paper an extended hierarchy of subgoal collections and different domains of operators are presented. Some subgoals are difficcult for all algorithms. Main of the work is a proposition of new algorithm. The proposal of another shift for state space searching finds solution of STRIPS problem by searching only one path in state-space graph for all subgoal types in block world. The price for one path searching is suboptimality of the solution. Two exemples explain proposition of the shift.