Path Database Guidance for Motion Planning

Amnon Attali, Praval Telagi, Marco Morales, Nancy M. Amato · 2025

Read Path Database Guidance for Motion Planning by Amnon Attali, Praval Telagi, Marco Morales, Nancy M. Amato (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05550.txt.

Introduction

Amnon Attali and co-authors guide robot motion planning with remembered paths in a 2025 paper. Planners often store solutions to past problems and reuse them. Most older methods paste the old path into the new problem or let it bias random sampling, both awkward fits with search algorithms.

Their method, Path Database Guidance, instead turns the database into a heuristic that tells the search which tree nodes to expand next. The database keeps updating as the search itself explores new ground. That makes the guidance compose cleanly with baseline planners. Simulations across varied environments show the pairing finding routes more effectively.

Catalog record

CREATORAmnon Attali, Praval Telagi, Marco Morales, Nancy M. Amato
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-05550

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Path Database Guidance for Motion Planning Amnon Attali, Praval Telagi, Marco Morales, Nancy M. Amato Abstract One approach to using prior experience in robot motion planning is to store solutions to previously seen problems in a database of paths. Methods that use such databases are characterized by how they query for a path and how they use queries given a new problem. In this work we present a new method, Path Database Guidance (PDG), which innovates on existing work in two ways. First, we use the database to compute a heuristic for determining which nodes of a search tree to expand, in contrast to prior work which generally pastes the (possibly transformed) queried path or uses it to bias a sampling distribution. We demonstrate that this makes our method more easily composable with other search methods by dynamically interleaving exploration according to a baseline algorithm with exploitation of the database guidance. Second, in contrast to other methods that treat the database as a single fixed prior, our database (and thus our queried heuristic) updates as we search the implicitly defined robot configuration space. We experimentally demonstrate the effectiveness of PDG in a variety of explicitly defined environment distributions in simulation. 1 1 footnotetext: Siebel School of Computing and Data Science at University of Illinois Urbana-Champaign, 201 N Goodwin Ave, Urbana, IL 61801 {aattali2, ptelag2, moralesa, namato}@illinois.edu 2 2 footnotetext: ITAM, México City, México. {marco.morales}@itam.mx. I Introduction Sampling-based motion planning (SBMP) algorithms use heuristics to guide search in the continuous robot configuration space (CSpace). This guidance commonly comes from ideas of expansiveness [ 22 , 14 ] , laziness [ 4 , 11 ] , or workspace guidance [ 13 , 8 ] . Such methods share some important features, namely that this guidance is quick to compute and updates as the implicitly defined CSpace is explored through collision checking. Another shared property is that they plan from scratch, making very few if no assumptions about the structure of the CSpace. Such generality can be desirable for its simplicity but is also limited in that it doesn’t take advantage of the more realistic scenario in which some information is already known about the search space. A simple example is that if certain obstacles in the environment are known to be static (e.g., the table to which a manipulator is attached), collision with these obstacles can be precomputed and used by the planner [ 17 , 25 ] . In this work we consider the setting in which offline we have access to samples from a distribution of environments, and must then plan online for a new environment and task sampled from this same distribution. Within reason, we are not concerned with runtime offline, but only how quickly (or with how little collision checking) we can solve this new task. One approach for encoding prior knowledge is to save solutions to previously seen problems as a database of paths (e.g., [ 3 ] ). Algorithms which follow this approach are differentiated by how they answer the following key questions: which paths are kept in the database, how is the database queried, and how is the queried path used (i.e., “repaired”) in the current CSpace. One additional universal feature is the use of some baseline planning from scratch (PFS) module such as RRT [ 22 ] to provide guarantees in case the database proves insufficient. Our main contribution is a path-database motion planner, Path Database Guidance (PDG). In contrast to prior work, which queries the database once with task -based information, PDG does so continuously using information gathered through collision checking. In other words, our database is iteratively filtered throughout the course of the search. Moreover, rather than directly pasting (e.g., [ 3 ] ) queried paths into the current CSpace or using them to learn sampling distributions (e.g., [ 6 ] ), we use the length of the queried path as an estimate of cost-to-go, i.e., as a heuristic to guide search tree growth. This means that rather than doing PFS in parallel to database guidance or sequentially as two distinct phases, we dynamically alternate between using the database or the PFS module to select which node to expand in an explore-exploit loop. Our perspective is that the specific set of paths in the database is a hyper-parameter, and thus we don’t provide a rule for determining which paths are kept in the database but rather propose that this hyper-parameter be determined through cross-validation on the offline dataset, as is standard in any learning-based approach. We evaluate PDG against both PFS baselines and standard existing database planners, whose parameters were all also tuned on the training dataset. The four algorithms are compared on three CSpace distributions for very different robots, demonstrating that PDG is fastest, most consistent, and uses 2-20 times fewer collision checks. II Background A robot motion planning (MP) problem consists of the tuple M=(r,E,s,t) , for robot r , environment E , and task (s,t) . Together, (r,E) describe the configuration space \mathcal{C} , a continuous space consisting of all possible configurations of r in E . This space is implicitly partitioned into two parts, \mathcal{C}_{free} and \mathcal{C}_{obs} . \mathcal{C}_{free} is the set of all valid configurations, and \mathcal{C}_{obs}=\mathcal{C}\setminus\mathcal{C}_{free} . A motion planner produces a valid path p_{s,t} from starting configuration s to goal configuration t , if one exists. Single query planners generally build a search tree T in \mathcal{C}_{free} by iteratively selecting a node and expanding it, using the primitive operation of collision checking (CC), in which a black box query provides the validity of a single configuration. Edges between nodes of the tree are validated by CC of sufficiently dense discrete configurations along them. Fig. 1: A simple example where Lightning performs poorly despite containing useful paths in its database. In this scenario where no single path solves the (s,t) planning problem on its own, Lightning chooses the path ( bolded ) with fewest collisions, throwing out all computation relating to the discarded paths (left). Since the entire difficulty of such a problem is encapsulated in navigating this narrow passage, repairing the broken segment with Bidirectional-RRT is approximately as difficult as solving the original problem (center). Finally the original path is combined with the repaired portion to solve the MP problem such that ultimately the database and PFS were used sequentially (right). There are many reasonable ways to evaluate a planner: • Runtime: a common and practical metric, but which can often depend on implementation details • Path length: we do not focus on this metric since in practice this quantity is often optimized in post-processing via smoothing operations • Number of CC configurations: CC is usually the most expensive component of motion planning, and also conceptually represents the amount of explicit information needed about the implicit \mathcal{C} to find a path • Number of CC batch calls: many collision checkers are parallelized, meaning they scale sub-linearly with the number of configurations queried in batch but also have some overhead, such as moving data onto a GPU Like [ 2 ] , in this work we consider the guided motion planning (GMP) problem, in which we have access to an offline dataset D=\{M_{i}\sim\mathcal{D}\}_{i=1}^{n} of n MP

Read the complete text