A framework for guided motion planning

Attali, Amnon David

Permalink

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

Description

Title

A framework for guided motion planning

Author(s)

Attali, Amnon David

Issue Date

2025-07-16

Director of Research (if dissertation) or Advisor (if thesis)

Amato, Nancy M

Doctoral Committee Chair(s)

Amato, Nancy M

Committee Member(s)

• LaValle, Steven M
• Morales, Marco
• Kavraki, Lydia E

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2025-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Amnon Attali

Owning Collections