Finding concise plans: Hardness and algorithms Conference Paper uri icon

abstract

  • This paper addresses the problem of generating the simplest plans that solve robotic planning problems. Most robotic planning algorithms are concerned with producing plans that minimize execution cost, or generalizations of such costs. Motivated by circumstances with severe computational resource limits (e.g., memory or communication constrained settings), we instead address the problem of producing concise plans. In this work, conciseness is a measure of plan size that reflects the complexity of representing the plan explicitly. We seek a plan with minimal representational size, subject to correctness and completeness. We introduce a planning algorithm that generates concise plans for planning problems that may involve both non-determinism and partial observability, and also show that finding the most concise plan is an NP-hard problem, excusing the possible sub-optimality of our algorithm's output. We describe an implementation of the algorithm, along with empirical results on the run time and solution quality for both manipulation and navigation problem domains. 2013 IEEE.

name of conference

  • 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems

published proceedings

  • 2013 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS)

author list (cited authors)

  • O'Kane, J. M., & Shell, D. A.

citation count

  • 3

complete list of authors

  • O'Kane, Jason M||Shell, Dylan A

publication date

  • November 2013