Finding concise plans: Hardness and algorithms

Jason M. O'Kane, Dylan A. Shell
In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems 2013.

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 problem 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.

Download

BibTeX

@inproceedings{OKaShe13b,
  author       = {Jason M. O'Kane and Dylan A. Shell},
  title        = {Finding concise plans: Hardness and algorithms},
  year	       = {2013},
  booktitle    = {Proc. IEEE/RSJ International Conference on Intelligent
		 Robots and Systems}
}

O'Kane's home page
O'Kane's publication list

Wed Sep 20 09:19:46 EDT 2017