MeshA*: Efficient Path Planning With Motion Primitives

Marat Agranovskiy, Konstantin Yakovlev · 2024

Read MeshA*: Efficient Path Planning With Motion Primitives by Marat Agranovskiy, Konstantin Yakovlev (2024) 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-2412-10320.txt.

Introduction

Robots and game agents often move by stitching together short, physically valid motion pieces called motion primitives. Marat Agranovskiy and Konstantin Yakovlev note that searching over the lattice those pieces create is slow, because each step branches into many options. Their algorithm, MeshA*, instead searches over plain grid cells, as the classic A* does, while fitting valid sequences of primitives into the cells along the way.

The change keeps the guarantees that matter: the search still finds a complete, optimal path when one exists. In tests it ran one and a half to two times faster than conventional lattice-based planning. The authors present MeshA* as a way to keep the physical realism of motion primitives without paying the usual search cost.

Catalog record

CREATORMarat Agranovskiy, Konstantin Yakovlev
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-10320

Browse the full library · About the Tower of Babel

Full text

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

MeshA*: Efficient Path Planning With Motion Primitives Marat Agranovskiy, Konstantin Yakovlev Abstract We study a path planning problem where the possible move actions are represented as a finite set of motion primitives aligned with the grid representation of the environment. That is, each primitive corresponds to a short kinodynamically-feasible motion of an agent and is represented as a sequence of the swept cells of a grid. Typically, heuristic search, i.e. A*, is conducted over the lattice induced by these primitives (lattice-based planning) to find a path. However, due to the large branching factor, such search may be inefficient in practice. To this end, we suggest a novel technique rooted in the idea of searching over the grid cells (as in vanilla A*) simultaneously fitting the possible sequences of the motion primitives into these cells. The resultant algorithm, MeshA*, provably preserves the guarantees on completeness and optimality, on the one hand, and is shown to notably outperform conventional lattice-based planning (x1.5-x2 decrease in the runtime), on the other hand. [email protected], [email protected] Code — https://github.com/PathPlanning/MeshAStar Introduction Kinodynamic path planning is a fundamental problem in AI, automated planning, and robotics. Among the various approaches to tackle this problem, the following two are the most widespread and common: sampling-based planning ( Karaman and Frazzoli 2011 ; Sakcak et al. 2019 ) and lattice-based planning ( Pivtoraiko and Kelly 2005 ; Pivtoraiko et al. 2009 ) . The former methods operate in continuous space, rely on the randomized decomposition of the problem into smaller sub-problems, and are especially advantageous in high-dimensional planning (e.g., planning for robotic manipulators). Still, they provide only probabilistic guaranties of completeness and optimality. Lattice-based planners rely on the discretization of the workspace/configuration space and provide strong theoretical guaranties with respect to this discretization. Consequently, they may be preferable when the number of degrees of freedom of the agent is not high, such as in mobile robotics, where one primarily considers the coordinates and the heading of the robot. In this work, we focus on the lattice-based methods for path planning in (x,y,\theta) . Lattice-based planning methods reason over the so-called motion primitives – the precomputed kinodynamically-feasible motions from which the sought path is constructed – see Fig. 1 . Stacked motion primitives form a state lattice , i.e., a graph, where the vertices correspond to the states of the agent and the edges correspond to the motion primitives. A shortest path on this graph may be obtained by algorithms, such as A* ( Hart et al. 1968 ) , that guarantee completeness and optimality. Unfortunately, when the number of motion primitives is high (which is not uncommon in practice), searching over the lattice graph becomes computationally burdensome. To this end, in this work, we introduce a novel perspective on lattice-based planning. Figure 1: Example of the path planning problem. The workspace is discretized to a grid, where the green cells correspond to the obstacles and the white ones represent the free space. The green cell with an arrow denotes the start state (position and heading), while the red cell – the goal one. The path is composed of the primitives (green and red segments). The swept cells are shown in blue. We leverage the assumption that the workspace is represented as an occupancy grid (a standard practice for path planning) and search over this grid in a cell-by-cell fashion to form a sequence of cells such that a sought path, i.e. a sequence of the motion primitives, may be fitted into this sequence of cells. We introduce a dedicated technique to reason simultaneously about the grid cells and the motion primitives that pass through these cells within the search process. Such reasoning allows us to decrease the branching factor, on the one hand, and to maintain the theoretical guarantees, on the other hand. Empirically, we show that the introduced path planning method, called MeshA*, is notably faster than the conventional A* and its lazy variant (this holds when the weighted heuristic is utilized as well). Related Work Various approaches to pathfinding consider a mobile agent’s kinodynamic constraints ( González et al. 2016 ) . One prominent group is sampling-based planning. Classical representatives include the RRT algorithm ( LaValle and Kuffner 2001 ) , which rapidly explores the configuration space, its anytime modification RRT* ( Karaman and Frazzoli 2010 ) aimed at converging to optimal solutions, and variants like Informed RRT* ( Gammell et al. 2014 ) , which incorporates heuristics, RRT-Connect ( Kuffner and LaValle 2000 ) for fast bidirectional planning, and \mathrm{RRT^{X}} ( Otte and Frazzoli 2014 ) for fast re-planning. Another direction is lattice-based planning, where a set of motion primitives that respect the constraints of the agent is constructed, and then a suitable sequence of these primitives is sought. Primitives can be generated using B-splines ( Flores and Milam 2006 ) , the shooting method ( Jeon et al. 2011 ) , the covering method ( Yakovlev et al. 2022 ) , learning-based techniques ( De Iaco et al. 2019 ) , and others. In this work, we follow the lattice-based approach, but assume the primitives are given in advance (for experiments, we use a simple Newton optimization method ( Nagy and Kelly 2001 ) ). Our focus is on reducing path planning search effort. Similar goals are addressed by approaches like Jump Point Search ( Harabor and Grastien 2011 ) , which significantly accelerates search on an 8-connected grid, and the well-known WA* ( Ebendt and Drechsler 2009 ) , which provides suboptimal solutions more quickly using weighted heuristics. Problem Statement Consider a point-sized mobile agent moving in a 2D workspace W\subset\mathds{R}^{2} composed of a free space W_{free} and obstacles W_{obs} . The workspace is tessellated into a grid, where each cell (i,j) is either free or blocked. State Representation . The state of the agent is defined by a 3D vector (x,y,\phi) , with coordinates (x,y)\in W and heading angle \phi\in[0,360^{\circ}) . We assume that the latter can be discretized into a set \Theta=\{\phi_{1},...,\phi_{k}\} , allowing us to focus on discrete states s=(i,j,\theta) that correspond to the centers of the grid cells (i,j)\in\mathds{Z}^{2} , with \theta\in\Theta . Motion Primitives . The kinematic constraints and physical capabilities of the mobile agent are encapsulated in motion primitives , each representing a short kinodynamically-feasible motion (i.e., a continuous state change). We assume these primitives align with the discretization, meaning that transitions occur between two discrete states, such as (i,j,\theta) and (i^{\prime},j^{\prime},\theta^{\prime}) . In other words, each motion starts and ends at the center of a grid cell, with its endpoint headings belonging to the finite set \Theta . Each primitive is additionally associated with the collision trace , which is a sequence of cells swept by the agent when executing the motion, and cost which is a positive number (e.g. the length of the primitive). For a given state s=(i,j,\theta) there is a finite number of motion primitives that the agent can use to move to other states. Moreover, we assume that there can be no more than one primitive leading to each other state, which corresponds to the intuitive understanding of a primitive as an elementary motion. We also consider that the space of discrete states, along with

Read the complete text