Body: <p>There are many methods and algorithms dealing with planning problems.</p>
  
  <p>If I understand correctly, according to Wikipedia, there are classical planning problems, with:</p>
  
  <ul>
  <li>a unique known initial state,</li>
  <li>duration-less actions,</li>
  <li>deterministic actions,</li>
  <li>which can be taken only one at a time,</li>
  <li>and a single agent.</li>
  </ul>
  
  <p>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.</p>
  
  <p>If actions are non-deterministic, according to Wikipedia, we have a Markow Decision Process (MDP), with:</p>
  
  <ul>
  <li><p>duration-less actions,</p></li>
  <li><p>nondeterministic actions with probabilities,</p></li>
  <li><p>full observability, or partial observability for POMDP</p></li>
  <li><p>maximization of a reward function,</p></li>
  <li><p>and a single agent.</p></li>
  </ul>
  
  <p>MDPs are mostly solved by Reinforcement Learning.</p>
  
  <p>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.</p>
  
  <p>Two questions: </p>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-06T23:36:57.897Z
Comments.Text: This is post contains interesting and useful information (in fact, I was one of the people that had upvoted it), but you're asking at least 3 distinct questions here (the title's question and the other 2 questions at the end of the post), each of which should be asked in its own separate post, which makes this post _too broad_. I would suggest that, if you're again/still interested in these topics, you try to ask more **specific** questions, each of which in its separate post.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-07T13:14:00.740Z
Comments.Text: I will reformulate. In the meantime I made significant progress in better understanding/answering the question.
Comments.UserDisplayName: 50k4
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-07T13:19:46.467Z
Comments.Text: I would suggest that you create a new post and delete this one. A new post can become hot, while this old post no.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><graph-theory><planning>
Title: How to choose method for solving planning problems?
UserDisplayName: 50k4
ThreadText: # How to choose method for solving planning problems?
  
  (Asked by: username_0 on 2019-01-23)
  
  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.
  
  **Tags:** reinforcement-learning, graph-theory, planning
  > **Comments:**
  > **username_1**: This is post contains interesting and useful information (in fact, I was one of the people that had upvoted it), but you're asking at least 3 distinct questions here (the title's question and the other 2 questions at the end of the post), each of which should be asked in its own separate post, which makes this post _too broad_. I would suggest that, if you're again/still interested in these topics, you try to ask more **specific** questions, each of which in its separate post.  
  > **username_0**: I will reformulate. In the meantime I made significant progress in better understanding/answering the question.  
  > **username_1**: I would suggest that you create a new post and delete this one. A new post can become hot, while this old post no.  
  
  ---
  
  ## 0 answers
  
  