Planning and execution through variable resolution planning Articles uri icon

publication date

  • September 2016

start page

  • 214

end page

  • 230

volume

  • 83

International Standard Serial Number (ISSN)

  • 0921-8890

Electronic International Standard Serial Number (EISSN)

  • 1872-793X

abstract

  • Generating sequences of actions - plans - for robots using Automated Planning in stochastic and dynamic environments has been shown to be a difficult task with high computational complexity. These plans are composed of actions whose execution might fail due to different reasons. In many cases, if the execution of an action fails, it prevents the execution of some (or all) of the remainder actions in the plan. Therefore, in most real-world scenarios computing a complete and sound (valid) plan at each (re-)planning step is not worth the computational resources and time required to generate the plan. This is specially true given the high probability of plan execution failure. Besides, in many real-world environments, plans must be generated fast, both at the start of the execution and after every execution failure. In this paper, we present Variable Resolution Planning which uses Automated Planning to quickly compute a reasonable (not necessarily sound) plan. Our approach computes an abstract representation - removing some information from the planning task - which is used once a search depth of k steps has been reached. Thus, our approach generates a plan where the first k actions are applicable if the domain is stationary and deterministic, while the rest of the plan might not be necessarily applicable. The advantages of this approach are that it: is faster than regular full-fledged planning (both in the probabilistic or deterministic settings); does not spend much time on the far future actions that probably will not be executed, since in most cases it will need to replan before executing the end of the plan; and takes into account some information of the far future, as an improvement over pure reactive systems. We present experimental results on different robotics domains that simulate tasks on stochastic environments. (C) 2016 Elsevier B.V. All rights reserved.

keywords

  • task planning; planning and execution; abstract representation; cognitive robotics; time heuristic-search; mobile robots; system; landmarks