Source-linked AI summary
Extended LASMP: Language Aided Subset Sampling Based Motion Planner for Drone Navigation
Saswati Bhattacharjee, Anirban Sinha, Mukulika Ghosh, Chinwe Ekenna
TL;DR
Uniform sampling can waste effort because it does not use directional intent in commands, motivating command-aware sampling for quadcopter navigation. Extended LASMP grounds language instructions into geometric constraints and guides sampling while preserving probabilistic completeness. In complex scenarios, it demonstrates superior reliability and command-following efficiency, and its guided sampling outperforms randomly oriented subset sampling on search-efficiency measures.
Problem
Uniform sampling often has poor sample efficiency in cluttered environments, and classical planners do not incorporate the directional intent of navigation commands into sampling.
Source: §I · p. 1Method
Extended LASMP maps language instructions to yaw-conditioned and altitude-aware constraints and uses command-aligned sampling with ray-guided switching for sequential execution.
Source: §I · pp. 1–2Results
Extended LASMP demonstrates superior reliability and command-following efficiency in complex scenarios; randomly oriented subset sampling takes approximately 68 times longer to converge and uses approximately 20 times more queries.
Source: §VI · p. 7, E. Ablation Study · p. 7Takeaways & Limitations
Guided sampling improves search efficiency over randomly oriented subsets while retaining probabilistic completeness.
Source: §I · p. 1, E. Ablation Study · p. 7Hardware evaluation under sensing uncertainty, dynamic-obstacle handling, online replanning, and richer semantic or multi-step reasoning remain future work.
Source: §VI · p. 7
Abstract
from arXiv · showhide
This paper proposes a command-aligned sampling distribution that incorporates navigation commands directly into the exploration process to improve the efficiency of sampling-based motion planning for quadcopters in three-dimensional environments. Inspired by the Language-Aided Subset Sampling Motion Planner, this paper extends command-aware subset sampling to aerial systems. Subset sampling is generalized to command-aligned regions, enabling structured 3D exploration while preserving probabilistic completeness. Natural language instructions are grounded into yaw-conditioned and altitude-aware geometric constraints using a prompt-based large language model for entity extraction and instruction validation. Extensive simulations in complex environments demonstrate that the proposed method generates collision-free, consistent trajectories while significantly reducing sampling effort compared to uniform RRT-based planners.
I. Introduction
Uniform sampling can waste effort in cluttered environments because it ignores directional intent in navigation commands. Extended LASMP incorporates those commands into aerial sampling while retaining probabilistic completeness.
I. Introduction
- Classical sampling-based planners can explore irrelevant regions because uniform sampling ignores the directional intent embedded in commands.This is especially problematic in cluttered environments, where uniform sampling often has poor sample efficiency.Source: §I · p. 1
- Extended LASMP extends LASMP to quadcopters in R3 × S1, restricting sampling to 3D subsets aligned with yaw-updated commands while preserving probabilistic completeness.Commands are interpreted as yaw updates followed by directional translation or vertical motion.Source: §I · p. 1
- Few-shot LLM-based named entity extraction maps instructions to yaw-conditioned and altitude-aware constraints, and checks for ambiguity or inconsistency.The approach does not require task-specific model retraining.Source: §I · p. 2
- The framework combines command-aware sampling with ray-guided switching for sequential command execution, and the paper reports improved sample efficiency, lower computational cost, and faster convergence than uniform-sampling planners.The paper also presents a probabilistic completeness analysis and a ROS2–PX4–Gazebo integration for physics-based execution.Source: §I · p. 2
A. Sampling-Based Motion Planning
- Sampling-based planners such as RRT and RRT-Connect are widely adopted for high-dimensional planning due to probabilistic completeness and computational efficiency, though uniform sampling can cause poor sample efficiency in large or cluttered environments.Source: A. Sampling-Based Motion Planning · p. 2
B. Informed and Biased Sampling
Prior sampling biases use geometric or cost-to-go heuristics, while command-aware planning can incorporate semantic direction into the sampling distribution. Extended LASMP addresses aerial planning in R3 × S1 while retaining probabilistic completeness.
B. Informed and Biased Sampling
- Informed RRT∗ samples around a feasible solution to improve path cost, while Dynamic-domain RRT reduces sampling near obstacles; neither incorporates structured task instructions into sampling.Extended LASMP instead aligns sampling subsets with yaw-updated command directions before finding a feasible solution.Source: B. Informed and Biased Sampling · p. 2
C. Kinodynamic and UAV Motion Planning
- For aerial robots, prior approaches address dynamic feasibility through closed-loop RRT, trajectory optimization, or motion primitives, but do not incorporate structured navigation commands into sampling.Extended LASMP focuses on the geometric planning layer in R3 × S1.Source: C. Kinodynamic and UAV Motion Planning · p. 2
D. Instruction-Conditioned Planning
- Language-based approaches map instructions to actions, but many rely on learned policies or treat language as an external task planner; Extended LASMP integrates language-derived constraints into geometric sampling while preserving probabilistic completeness.The overview describes a language module for grounding instructions and a planner module for computing the path.Source: D. Instruction-Conditioned Planning · p. 2, Figure 2 · p. 3
III. Problem Statement
- The planning state combines 3D position and yaw, and the task is to find a collision-free trajectory from a start state to a goal state under an ordered command sequence.The state space is D ⊂ R3 × S1.Source: §III · p. 2
{STRAIGHT, LEFT, RIGHT, UP, DOWN,
The planning problem is to produce a collision-free trajectory that executes navigation commands in order. The methodology grows a search tree using command-aligned sampling and ray-based command switching.
{STRAIGHT, LEFT, RIGHT, UP, DOWN,
- The trajectory must execute commands in order: LEFT and RIGHT update yaw after translation, STRAIGHT moves forward, UP and DOWN move vertically, and turn-back or in-place turns update yaw without translation.The objective is a collision-free trajectory from the start state to the goal state.Source: {STRAIGHT, LEFT, RIGHT, UP, DOWN · p. 3
IV. Methodology
- The planner has a language-grounding module and a planner module that computes a path from the start location to the goal based on the instruction.It incrementally builds a search tree in D ⊂ R3 × S1 while respecting the ordered command sequence.Source: §IV · p. 3
- During tree expansion, samples come from dynamically defined subsets aligned with the current command, focusing exploration on relevant regions while preserving probabilistic completeness.The planner grows a tree rooted at the start state as valid nodes become available.Source: §IV · p. 3
A. Command Interpretation
Commands specify desired motion directions and may update yaw before translation. The planner samples from a subset oriented along the command, parameterized by forward, lateral, and vertical extents.
A. Command Interpretation
- Each command ϕj induces a desired motion direction, and ψ(x) denotes the yaw component of state x.UP and DOWN correspond to pure vertical motion; the heading vector is defined following a yaw update.Source: A. Command Interpretation · p. 3
B. Command-Aligned Sampling Subsets
- To expand a node, the planner draws samples from a subset centered at its position and oriented along the current command direction.The subset uses forward, lateral, and vertical extents h, w, and d, and restricts samples to states forward-aligned with the commanded motion.Source: B. Command-Aligned Sampling Subsets · p. 3
C. Tree Expansion
Extended LASMP grows a tree by sampling within command-aligned subsets, advances through ordered commands when a forward ray detects an opening, and grounds validated language instructions into navigation entities.
C. Tree Expansion
- The planner samples uniformly from a command-aligned subset, steers toward the sample, and adds the new state only when the connecting path is collision-free.The subset is constructed using the current command direction and yaw update.Source: C. Tree Expansion · p. 3, E. Natural Language-Based Instruction… · p. 4
D. Command Execution and Switching
- A ray in the next command’s direction checks for an opening; if none intersects an obstacle within look-ahead distance L, the planner switches commands.The ray is cast from the new state, and the criterion identifies free space such as corridors or intersections.Source: D. Command Execution and Switching · p. 4
E. Natural Language-Based Instruction Grounding
- An error filter flags misleading entities, typos, and ambiguous directions, requesting corrected input before forwarding valid instructions to extraction.The validated instruction and few-shot demonstrations condition the language model’s structured output.Source: E. Natural Language-Based Instruction… · p. 4
- The generated sequence is parsed into entity–label pairs, which are mapped to navigation primitives for planning.The motion-related entities are extracted using ChatML-based few-shot prompting.Source: E. Natural Language-Based Instruction… · p. 4
A. Experimental Setup
The experiments use four simulated building environments and compare planner metrics across them; the language-grounding section illustrates prompt-based extraction of navigation commands.
A. Experimental Setup
- The setup loads Qwen3-1.7B for the language module and uses the GPU for language processing while planning runs on the CPU.The machine is described as an Intel i7 system with 16 GB RAM and an NVIDIA GeForce RTX GPU.Source: A. Experimental Setup · p. 4
B. Natural Language grounding
- The illustrated ChatML prompt structures messages by role, with system behavior, user task, and an optional assistant example.The example prompt asks for navigation-turn entities such as LEFT, RIGHT, UP, and DOWN.Source: Figure 3 · p. 5, A. Experimental Setup · p. 5
A. Experimental Setup
- The evaluation includes three two-story environments and one single-story environment, with environments varying in obstacle density and corridor width.The described setup uses ROS2-Gazebo simulation with PX4 for low-level flight control.Source: A. Experimental Setup · p. 5, Figure 4 · p. 5
B. Natural Language grounding
- Table I reports lower-is-better quantitative comparisons across four environments, averaged over 10 runs.The caption states that measurements were executed on an i7 processor in Ubuntu 24.04 LTS.Source: Table I · p. 5
- The language-grounding example validates an instruction, extracts motion entities, and maps the resulting entity–label pairs to executable navigation primitives.Qwen’s entity identification was evaluated on 100 erroneous navigation instructions and reported 75% accuracy.Source: B. Natural Language grounding · p. 5
C. Performance Evaluation of Extended LASMP
Across four environments, Extended LASMP substantially reduced search-tree nodes and random-state queries relative to RRT, RRT*, and RRTConnect. Computation time remained competitive, while paths could be longer in keeping with the planner’s instruction-following objective.
C. Performance Evaluation of Extended LASMP
- The evaluation averaged 10 independent runs and reported start and goal configurations, instruction-derived turn lists, and algorithm parameters.Computed paths were illustrated for each environment.Source: C. Performance Evaluation of Extended… · p. 5
- Random-state queries fell by 98.0%–99.5% versus RRT, 96.7%–99.2% versus RRT*, and 93.5%–98.9% versus RRTConnect.The evaluation compared Extended LASMP against planners using uniform sampling.Source: C. Performance Evaluation of Extended… · p. 5
- Extended LASMP reduced nodes by 93.1%–98.7% versus RRT, 90.2%–98.4% versus RRT*, and 70.6%–96.7% versus RRTConnect across four environments.Results were averaged over 10 independent runs; Fig. 6 compares nodes, queries, computation time, and path length.Source: C. Performance Evaluation of Extended… · p. 5, Figure 6 · p. 6
- Paths were approximately 2% longer than RRT and 20% longer than RRT*, while computation time was lowest in Env1 and slightly higher than RRT-Connect elsewhere.The authors state the planner prioritizes user-provided navigation instructions over strict path optimality.Source: C. Performance Evaluation of Extended… · p. 6
D. Simulation Setup and Execution in ROS2 and Gazebo
ROS2–Gazebo simulations executed command-aware trajectories through a PX4 flight-control stack, and the ablation results favored guided over randomly oriented subset sampling for search efficiency. The conclusion identifies hardware testing under sensing uncertainty and extensions for dynamic obstacles and richer instructions as future work.
D. Simulation Setup and Execution in ROS2 and Gazebo
- In ROS2–Gazebo, command-aware sampling produced dynamically executable trajectories tracked through ROS2–PX4; infeasible turn lists trigger fallback to standard RRT.The planner publishes smoothed and interpolated waypoints tracked at 50 Hz; ray-based opening detection switches commands when the look-ahead is clear.Source: D. Simulation Setup and Execution in… · pp. 6–7, Figure 7 · p. 7
E. Ablation Study
- Against randomly oriented subset sampling, Extended LASMP had approximately 68 times lower convergence time, seven times fewer nodes, and about 20 times fewer queries, with comparable path length.The random-orientation planner still found a feasible path; the ablation also found no observable performance difference when the LLM was bypassed and the turn list hard-coded.Source: E. Ablation Study · p. 7, Table IV · p. 7
VI. Conclusions
- The conclusion characterizes Extended LASMP as a robust planner prioritizing successful instruction execution over path optimality.Future work includes hardware deployment under sensing uncertainties, dynamic-obstacle handling, online replanning, and richer semantic instructions with multi-step reasoning.Source: §VI · p. 7
VII. Appendix
Under stated clearance, steering, subset-coverage, and sampling-density assumptions, Extended LASMP is probabilistically complete: if a feasible path exists, it finds a collision-free path with probability approaching 1 as iterations increase.
A. Probabilistic Completeness of Extended LASMP
- The guarantee assumes a strongly δ-clear feasible path, suitable steering, command-aligned subset coverage of successive milestones, and sampling density bounded below by a positive constant.The collision-free space is also assumed open and measurable.Source: A. Probabilistic Completeness of… · p. 7
- With a feasible path, the probability of reaching the goal approaches 1 as the number of iterations grows.The proof bounds the failure probability for each next milestone region by (1 − q)^N, with a finite number of regions.Source: A. Probabilistic Completeness of… · pp. 7–8
- Finite milestone regions along the path support progress: when a milestone is reached, the next region lies in a command-aligned subset, giving a positive chance of a valid extension.The proof uses the lower-bounded sampling density and collision-free local connections between successive regions.Source: A. Probabilistic Completeness of… · p. 8
1) Corollary (Mixture Sampling):
With ε > 0, the mixture sampling distribution gives every open subset of Dfree nonzero sampling probability, implying probabilistic completeness under standard RRT assumptions.
1) Corollary (Mixture Sampling):
- With ε > 0, every open subset of Dfree has nonzero sampling probability, so probabilistic completeness follows from standard RRT assumptions.The supplied passage introduces this as a mixture-sampling corollary.Source: 1) Corollary (Mixture Sampling) · p. 8