A framework for guided motion planning

The Robotics search problem is computationally difficult, motivating practical approaches that sacrifice generality in favor of effective solutions in realistic scenarios. In this work we aim to unify how one branch of Robotics algorithms, namely the family of Sampling-Based Motion Planning methods, exploit heuristics to do guided search. In order to unify how different methods guide search we start with a simple observation - the Motion Planning problem definition is insufficient for answering questions regarding where guidance comes from, when is it effective, and how is it used. Thus our framework for Guided Motion Planning (GMP) involves a modified problem definition that implies guidance comes from prior experience which is distilled into a data structure we call the Guiding Space. We then propose a simple Guided Search algorithm that uses a Guiding Space, and the heuristics it provides, to do motion planning. By making experience a part of the problem definition we make aspects of motion planning that are traditionally done informally, such as algorithm selection or heuristic design, an explicit component of guided planning. Most of the work we present can be viewed as justifying the proposed framework. To demonstrate generality we show how otherwise incomparable methods in the literature can be brought closer by framing them with our language, including a wide variety of methods that seem to have nothing to do with heuristics. To demonstrate applicability we show how implementing existing ideas from the literature for planning from experience within our framework leads to improved algorithms. Finally we propose metrics for evaluating and learning guidance, showing how this language of learning heuristics from experience is useful for standardizing the evaluation and design of new algorithms, that a simple re-framing can highlight properties of existing algorithms that are otherwise obscured when computing holistic performance.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Attali, Amnon David

Contributors dc:contributor

• Amato, Nancy M.
• Amato, Nancy M
• LaValle, Steven M
• Morales, Marco
• Kavraki, Lydia E.

• Sampling Based Motion Planning
• Guided Motion Planning
• Robotics
• Heuristics
• Experience-based Planning

Statement dc:rights

• Copyright 2025 Amnon Attali

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129848

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129848