There are many methods and algorithms dealing with planning problems.

If I understand correctly, according to Wikipedia, there are classical planning problems, with:

  • a unique known initial state,
  • duration-less actions,
  • deterministic actions,
  • which can be taken only one at a time,
  • and a single agent.

Classical planning problems can be solved using classical planning algorithms. The STRIPS framework for problem description and solution, using backward chaining) of the GraphPlan algorithm can be mentioned here.

If actions are non-deterministic, according to Wikipedia, we have a Markow Decision Process (MDP), with:

  • duration-less actions,

  • nondeterministic actions with probabilities,

  • full observability, or partial observability for POMDP

  • maximization of a reward function,

  • and a single agent.

MDPs are mostly solved by Reinforcement Learning.

Obviously, classical planning problems can also be formulated as MDPs (with state transition probabilities of 1, i.e. deterministic actions), and there are many examples (e.g. some OpenAI Gyms), where these are successfully solved by RL methods.

Two questions:

  1. Are there some characteristics of a classical planning problem, which makes MDP formulation and Reinforcement Learning a better suiting solution method? Better suiting in the sense that it finds a solution faster or it finds the (near)optimal solution faster.

  2. How do graph search methods like A* perform with classical planning problems? Does STRIPS with backward chaining or GraphPlan always outperform A*? Outperform in the sense of finding the optimal solution faster.


The keyword you're searching for is “informed search”. Informed search is classical planning plus heuristics for speed up the graph traversal. A general rule is, that non-informed search is slow, while informed search is fast.

Algorithm which are based on symbolic planning like STRIPS are faster than normal A*. A* has also a heuristic but only a smaller one. Outperforming STRIPS is possible with macro actions, which increases the amount of heuristics further, which is available in the planner. A bad idea would be to increase the amount of heuristics to much into the direction of fuzzy sets. This kind of grounded motion primitives results into low quality papers and a missing mathematical understanding of Artificial Intelligence.

  • $\begingroup$ I am familiar with informed search and jump point search. (But you are right, probably informed search would be better in the text then A*). An comments on the MDP part? when would it be useful to solve a deterministic planning problem as an MDP with reinforcement learning? $\endgroup$ – 50k4 Jan 23 '19 at 22:30
  • $\begingroup$ @50k4 MDP is about probability theory, right? It was invented by Blaise Pascal (1623-1662) and describes reality under an analytical point of view. This fits very well to classical understanding of science which is common in higher education and is a here to stay paradigm. $\endgroup$ – Manuel Rodriguez Jan 24 '19 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.