Forward Search with Backward Analysis Academic Article uri icon

abstract

  • We describe a new forward search algorithm for classical planning. This algorithm attempts to maintain a focused search, expanding states using only a subset of the possible actions. Given a state s that was obtained by applying action a to state s, we prefer to apply in s only actions a that require some effect of a which we call forward actions. As this is incomplete, we must also consider actions a that supply some other precondition of a and actions a that supply preconditions to a and so on. We call these backward actions, as identifying the relevant actions requires backward reasoning. We show that by giving high priority to the forward actions a we get improved performance in many domains. The resulting algorithm can be viewed as building on the classic idea of means-ends analysis [Newell and Simon, 1961]. One crucial open problem that arises is how to prioritize the search for backward …

publication date

  • June 1, 2017