AI Research Portal

This paper addresses the path planning problem for mobile agents using motion primitives aligned with a grid representation of the environment. It introduces MeshA*, a novel technique that searches over grid cells while simultaneously reasoning about motion primitives. The core idea is to define an "extended cell" that combines a grid cell with a configuration of primitives passing through it, allowing for a cell-by-cell search. MeshA* is shown to preserve guarantees on completeness and optimality, and empirically outperforms conventional lattice-based planning (LBA*) by achieving a 1.5x to 2x decrease in runtime.

The paper identifies the following bottlenecks in existing lattice-based path planning methods:

Inefficient Search due to Large Branching Factor: When the number of motion primitives is high, searching over the state lattice graph (where vertices are agent states and edges are motion primitives) becomes computationally burdensome due to a large branching factor.
Computational Burden of Expansion Procedure: The expansion procedure in A*-like algorithms, which involves considering all applicable primitives, checking validity, computing costs, and filtering duplicates, is the main building block and degrades performance as the number of primitives increases.

The key contributions claimed by the paper are:

Introduction of a novel technique, MeshA*, that searches over grid cells simultaneously fitting sequences of motion primitives into these cells.
Development of a dedicated technique to reason simultaneously about grid cells and motion primitives within the search process.
Proof that MeshA* provably preserves guarantees on completeness and optimality.
Empirical demonstration that MeshA* notably outperforms conventional lattice-based planning (LBA*), achieving a 1.5x to 2x decrease in runtime.
Introduction of a novel search space, the mesh graph, which enables cell-level search-space pruning techniques unavailable to LBA*.

The method, MeshA*, re-frames lattice-based path planning by searching over grid cells rather than directly over motion primitives.

Search Space Elements:

State Representation: The agent's state is a 3D vector (x, y, φ), where (x, y) are grid coordinates and φ is a discretized heading angle from a set Θ = {1, ..., k}.
Motion Primitives: These represent short kinodynamically-feasible motions, starting and ending at grid cell centers with endpoint headings in Θ. Each primitive has a collision trace (sequence of swept cells) and a cost.
Extended Cell: The core element of the search space is an extended cell u = (i, j, Ψ), formally defined as a tuple of a specific grid cell (i, j) and a configuration of primitives Ψ. A configuration of primitives Ψ is a set of pairs {(prim₁, k), ..., (primn, k)}, where prim is a motion primitive from a control set and k is an index indicating that the (i, j) cell is the k-th cell in prim's collision trace. This captures information about both the grid cell and the primitives passing through it.
Initial Configuration: For a given heading θ, the initial configuration Ψθ is defined as Ψθ = {(prim₁, 1), ..., (primr, 1)}, where prim₁, ..., primr are all primitives from the control set with initial heading θ.

Successor Relationship: Successors of an extended cell u = (i, j, Ψ) are obtained by taking "steps" along each primitive from the current configuration.

Displacement: The change in grid coordinates when transitioning from the k-th cell to the (k + 1)-th cell in the collision trace of prim is denoted by Δprim_k = (i' - i, j' – j).
Initial Successor (Case 1): An extended cell v = (i', j', Ψθ) is an initial successor of u if there exists a (prim, k) ∈ Ψ such that k = Uprim - 1 (the primitive is at its final step), Δprim_k = (i' - i, j' – j), and prim ends at angle θ. This means a primitive completes its motion, and a new bundle of primitives starting with the same angle θ can extend from v.
Regular Successor (Case 2): If a primitive (prim, k) ∈ Ψ does not terminate (k < Uprim - 1), it contributes to a regular successor. The displacement (a, b) = Δprim_k is used to group all non-terminating primitives that lead to the same next grid cell (i+a, j+b). The configuration Ψ' for this successor v = (i+a, j+b, Ψ') is formed by collecting (prim, k+1) for all such primitives.

Transition Costs: The transition cost cost(u, v) from an extended cell u to its successor v is defined as: cost(u, v) = {Cprim, if v is an initial successor; 0, otherwise} where Cprim is the cost of the primitive prim that terminates at v.

Search Algorithm: MeshA* applies the standard A* algorithm to search for a path on the constructed mesh graph. The mesh graph's vertices are extended cells, and edges are defined by the successor relationship.

Heuristic Function: MeshA* uses a heuristic h(u) based on an admissible and consistent lattice-based A* heuristic hLBA*. h(u) = {hLBA*(i,j,θ), if u is initial with Ψ = Ψθ; min(uo,co)∈Finals(u){h(uo) + co}, otherwise} where Finals(u) is the set of (u_prim, c_prim) pairs, with u_prim being the initial extended cell where an instance of prim passing through u terminates, and c_prim its cost.

Workspace Representation: 2D workspace W ⊂ R² tessellated into a grid, with cells (i, j) being either free or blocked.
Agent State: (x, y, φ), where (x, y) are grid coordinates and φ is a heading angle discretized into a set Θ = {1, ..., k}.
Motion Primitives: Precomputed kinodynamically-feasible motions. For experiments, a simple Newton optimization method (Nagy and Kelly 2001) is used to generate them.
Control Set: A canonical set of primitives from which all others can be obtained through parallel translation.
Collision Trace: A sequence of cells swept by the agent when executing a motion primitive.
Path Cost: Sum of the costs of its constituent primitives.
Heuristic Search Algorithm: Standard A* algorithm is used on the mesh graph.
Heuristic Weights: Experiments test heuristic weights w ∈ {1, 1.1, 2, 5, 10}.
Implementation: All algorithms (LBA*, LazyLBA*, MeshA*) are implemented in C++ with identical data structures (e.g., priority queue) and underlying A* logic.
Optimization: Includes g-value pruning (avoiding exploration of states with known better g-values). To avoid DecreaseKey operations, all successors are added to OPEN, but discarded if the state is already in CLOSED.
Hardware: All experiments conducted on AMD EPYC 7742.
Motion Model: Car-like motion model used to generate 24 motion primitives for each of 16 different headings.

Datasets: Experiments conducted on four MovingAI benchmark maps:
- Labyrinth (size: 768x1024, total tests: 13320)
- ht_0_hightown (size: 514x514, total tests: 4200)
- Moscow_0_512 (size: 512x512, total tests: 5490)
- AR0304SR (size: 512x512, total tests: 4020)
Metrics:
- Runtime (median, relative to LBA*)
- Processed cells (total cells in collision traces examined, relative to LazyLBA*)
- Solution Cost (median, relative to optimal cost)
Baselines:
- LBA* (Lattice-based A*): Standard A* on the state lattice.
- LazyLBA*: LBA* with lazy collision-checking.
Numeric Results:
- Runtime: MeshA* consistently outperforms baselines.
  - For w = 1, MeshA* consumes on average 60%-80% of LBA* runtime (up to 1.5x speed-up).
  - With weighted heuristics (w > 1), MeshA* shows up to 2x speed-up.
  - LazyLBA* consistently performs worse than LBA*.
- Processed Cells: MeshA* processes only ≈ 50% of the cells that LazyLBA* examines.
- Solution Cost (ht_0_hightown map, median relative to optimal cost):
  - LBA*: w=1 (100.0), w=2 (105.7), w=5 (110.0), w=10 (113.2)
  - LazyLBA*: w=1 (100.0), w=2 (105.7), w=5 (110.0), w=10 (113.2)
  - MeshA*: w=1 (100.0), w=2 (109.2), w=5 (117.6), w=10 (122.3)
Runtime/Training Cost: Not stated in the paper.

Increased Solution Cost with Weighted Heuristics: MeshA*'s solution costs increase slightly more with rising heuristic weight w than LBA*'s. This is attributed to MeshA* computing the heuristic at every cell, whereas LBA* computes it only twice per primitive, leading to a more pronounced effect of w on MeshA*.
Applicability to Higher Dimensions: While the core idea of MeshA* is applicable to pathfinding in 3D and cases with additional discretized variables, adapting MeshA* to such setups is a prominent direction for future work, implying it is not directly implemented or evaluated for these scenarios in the current work.

Method evidence: "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." (section: Introduction)
Result evidence: "For w = 1, it consumes on average 60%-80% of the LBA* runtime (depending on the map). That is, the speed-up is up to 1.5x. When the heuristic is weighted, this gap gets even more pronounced, and we can observe x2 speed-up." (section: Empirical Evaluation)
Limitation evidence: "Despite having considered path planning in 2D when the agent's state is defined as (x, y, θ), the idea that stands behind MeshA* is applicable to pathfinding in 3D as well as to the cases where the agent's state contains additional variables as long as they can be discretized. Adapting MeshA* to such setups is a prominent direction for future work." (section: Conclusion)

MeshA*: Efficient Path Planning with Motion Primitives

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures