Execution cost optimization for hierarchical planning in the now

For robots to effectively interact with the real world, they will need to perform complex tasks over long time horizons. This is a daunting challenge, but human ability to routinely solve these problems leads us to believe that there is underlying structure we can leverage to find solutions. Recent advances using hierarchical planning [19] have been able to solve these problems by breaking a single long-horizon problem into several short-horizon problems. While this approach is able to effectively solve real world robotics planning problems, it makes no effort to account for the execution cost of an abstract plan and often arrives at poor quality plans. In this thesis, we analyze situations that lead to execution cost inefficiencies in hierarchical planners. We argue that standard optimization techniques from flat planning or search are likely to be ineffective in addressing these issues. We outline an algorithm, RCHPN, that improves a hierarchical plan by considering peephole optimizations during execution. We frame the underlying question as one of evaluating the resource needs of an abstract operator and propose a general way to approach estimating them. We introduce the marsupial logistics domain to study the effectiveness of this approach. We present experiments in large problem instances from marsupial logistics and observed up to 30% reduction in execution cost when compared with a standard hierarchical planner.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Hadfield-Menell, Dylan

Advisor dc:contributor.advisor

• Leslie Pack Kaelbling and Tomás Lozano-Pérez.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/85421

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/85421