Explore chapters and articles related to this topic
The Current State of AI Planning Research
Published in Takushi Tanaka, Setsuo Ohsuga, Moonis Ali, Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2022
The Graphplan algorithm of Blum and Furst, described above, relies less on regression than most planners do. Their algorithm would construct a prosgression graph representing all the possible milling operations, then try to extract a plan from it. The extraction phase does use regression, but of a “propositional” variety; no variables are bound during this phase. Unfortunately, Graphplan does not allow actions’ effects to be context-dependent. Hence the action mill (object, volume) would have to be replaced with a variant in which every condition that can influence an effect is encoded as an argument to the action: mill (object, volume, existing-volumes, ex-isting faces, …).
A hybrid re-composition based on components and web services
Published in International Journal of Computers and Applications, 2020
Khadidja Bentlemsan, Djamal Bennouar, Dalila Tamzalit, Khaled Walid Hidouci
The GraphPlan iteratively expands itself one layer at a time, layers alternate at each iteration i = (1 … n) a set of propositions Pi and a set of actions Ai, the GraphPlan construction phase builds the GraphPlan from the initial layer (layer 0), Nodes in layer 0 correspond to set of propositions P0 to denote the initial state of a planning problem. The GraphPlan loops over the repository to add relevant actions; for example, Layer 1 consists of an action level, A1 and a proposition level P1 [17]. A1 is the set of actions where preconditions are nodes in P0, and P1 is the union of P0 and the sets of effects of actions in A1. An action node in A1 is connected by incoming precondition arcs to preconditions in P0, and it is connected by outgoing arcs to in P1. This process ends when no more action can be added in the action layer of the GraphPlan and we called it the fixed layer [18]. It takes a polynomial time depending on the length of initial state and the number of actions implicated in this process [8]. If the goal is contained in the fixed layer, we say the goal is reached and a solution exists; thus, HACS composition is converted into a reachable problem. Otherwise, no solution exists.
PDDL4J: a planning domain description library for java
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2018
Graphplan was the first planner that introduced a planning graph structure (Blum & Furst, 1997). The extraction of a solution plan from the planning graph is a backward search from the last proposition level containing the goal to the first proposition level, which is the initial state of the planning problem. For each goal proposition at the last level of the planning graph, the search procedure non-deterministically chooses a set of mutex free actions producing the goal propositions. If such a set exists, the new goal becomes the union of the preconditions of these actions. Otherwise, there is no solution, the search procedure backtracks and tries another set of mutex free actions. The search is exponential in time. More information about Graphplan implementation in PDDL4J is available in IPP planner papers (Koehler, 1999; Koehler et al., 1997).