LLM-Enhanced Path Planning: Safe and Efficient Autonomous Navigation with Instructional Inputs

In plain words

A robot in an industrial workspace is told, in ordinary language, to fetch an item from a shelf and avoid the repair area on the way. A path planner alone knows the map but not the words. This paper puts a language model between the two. The model reads the instruction and decides what should change on the robot's map: go to this spot, make that area expensive to cross, or go back to the original map. The planner then does the actual route search on the updated map.

The map is a grid of cells that are free or occupied. Because the language model only edits the map and the goal, the route search stays a conventional, checkable step. When something changes, such as a repair zone appearing or a pedestrian blocking a lane, the map is updated and the route is planned again. The authors test this in a simulated industrial workspace and compare it with the classic A* search.

TL;DR

• Adds an LLM front end to grid-map path planning. The LLM turns a natural-language instruction into map edits and goal changes, which are then executed step by step with replanning.
• Evaluated only in simulation (Husky-UR3 in Gazebo), with three open LLMs (Mistral, Llama3, Llama3.1) on four strategy phrasings, against A* on the same grid.
• Headline numbers are author-reported. The LLM prompt, the cost values and the search algorithm the planner uses are not given, so the result is hard to reproduce.

Problem

Classic planners such as A* and RRT* find good routes on a static map, but they lack semantic understanding and cannot take a natural-language instruction such as "avoid the repair area" §1 §3. The authors define the task as instruction-based navigation on a two-dimensional occupancy grid, where each cell is free (0) or occupied (1), and the robot observes the grid, its pose and a set of detected semantic landmarks at every step §3. A plan must respect the instruction's meaning, avoid obstacles, including ones detected during the run, and adapt when the environment changes §3.

The paper also states that prior LLM-based navigation methods often rely on high-fidelity sensors and complete maps, and that they tend to plan once from the first observation §1 §2.

Method

Overview. DCIP (Dynamic Chain of Instruction-based Planning) takes an instruction and the first observation, produces an initial action sequence, and then repeats: observe, update goals and constraints, generate new actions, and execute them while updating the grid alg. 1 §4.

Step 1. Instruction dissection. A natural-language understanding (NLU) module splits the instruction into a task definition (the goal, for example "navigate to Shelf 3"), an action format (the action names) and semantic constraints (for example "avoid repair area" or "prefer open lanes") §4.1. The equation in §4.1 is written as a mapping from I to these three parts.

Step 2. Action types. The paper defines the set of actions as functions that transform the grid or set a goal. The three action types are:

• Map resetting: the grid is replaced by its initial state G_0 §4.2.
• Cost modification: cells inside a region R get a cost C_modify, and cells outside R keep their current cost §4.2.
• Goal setting: a goal location (x_goal, y_goal) is set §4.2.

Each action a is written as a function f_a(G_t, θ_a), where θ_a holds its parameters (the region R or the goal coordinates). Parsing an instruction gives a subset A of these actions, which are applied in turn §4.3.

Step 3. Worked example. For the instruction "navigate to the target while avoiding obstacles", the NLU module is said to extract SET_GOAL and MODIFY_COST. SET_GOAL sets a new goal. MODIFY_COST sets the cost of obstacle cells to a high value C_high and leaves other cells unchanged §4.3.

Step 4. Grid and goal updates. Map updates are described as a single combined rule: the multimodal data (semantic landmarks from visual inputs) plus the parsed actions give an updated occupancy grid §4.4.

Execution loop. The paper describes the loop in the algorithm below alg. 1.

# Dynamic Chain of Instruction-based Planning  [alg. 1]
# Input:  instruction (text), first observation (grid, pose, landmarks)
# Output: actions, executed in order on the robot

def dcip(instruction, observation_0):
    # Parse the instruction into goals and constraints  [alg. 1] [§4.1]
    goals, constraints = parse_instruction(instruction)
    # Generate the initial action sequence from I and O_0  [alg. 1]
    actions = generate_actions(instruction, observation_0)
    # Execute each action, then update the grid  [alg. 1] [§4.3]
    for action in actions:
        execute(action)
        grid = update_grid(grid, action)
    # Repeat until the task is complete; the stop test is not stated  [alg. 1]
    while not task_completed():
        # Capture the current observation O_t  [alg. 1]
        observation = capture_observation()
        # Update goals and constraints from I and O_t  [alg. 1]
        goals, constraints = update_goals(instruction, observation)
        # Generate a new action sequence and run it the same way  [alg. 1]
        actions = generate_actions(instruction, observation)
        for action in actions:
            execute(action)
            grid = update_grid(grid, action)

The action semantics, written out:

# Apply one action to the grid and the goal  [§4.2] [§4.3]
def apply_action(grid, goal, action, params):
    # Map resetting: restore the initial grid G_0  [§4.2]
    if action == "RESET_MAP":
        grid = initial_grid
    # Cost modification: set cells in the region to a cost  [§4.2] [§4.3]
    # The cost is C_modify in §4.2 and C_high in §4.3; no value is given
    elif action == "MODIFY_COST":
        for cell in params.region:
            grid[cell] = params.cost
    # Goal setting: replace the goal with the new coordinates  [§4.2] [§4.3]
    elif action == "SET_GOAL":
        goal = params.goal
    return grid, goal

The grid equations, as the paper writes them:

E(x, y) \in \{0, 1\} §3

where 0 is free space and 1 is occupied space §3.

G' = f_{\text{reset}}(G_t) = G_0 §4.2

G'(x, y) = \begin{cases} G_t(x, y), & (x, y) \notin R \\ C_{\text{modify}}, & (x, y) \in R \end{cases} §4.2

G_{\text{goal}} = (x_{\text{goal}}, y_{\text{goal}}) §4.2

G'(x, y) = \begin{cases} G_t(x, y), & (x, y) \notin \text{Obstacles} \\ C_{\text{high}}, & (x, y) \in \text{Obstacles} \end{cases} §4.3

Hyperparameters

Results

Author-reported. Setup: a Gazebo simulation of a Husky-UR3 robot in an industrial workspace with shelves, storage, repair zones and pedestrians §5.3. Pick-and-place instructions were written by volunteers and fed into DCIP §5.4. Table 1 scores the three LLMs on instruction adherence, completeness and safety. The values are percentages as printed tab. 1.

Table 2 gives the path-search metrics for A* and DCIP on the same grid, with the model and strategy for each DCIP row tab. 2. Path cost uses zone weights for DCIP (see Pitfalls). Search time is in seconds.

Summary of the figures and text:

• Path length. DCIP paths have length 177 to 179 against 177 for A*, so the paper reads them as comparable to A* §5.1.1 tab. 2.
• Turns. DCIP turns range from 9 to 37 against 66 for A* tab. 2.
• Nodes and time. Nodes expanded and search time for DCIP range from 366 to 13,967 and from 0.0093 s to 0.3978 s, against 2,254 nodes and 0.1253 s for A*. The Llama models in quick mode are the fastest §5.1.1 tab. 2.
• Scaling. On grids enlarged 1x to 10x, the nodes expanded and search time for A* and DCIP (Llama3.1, Balance strategy) are plotted, not tabulated. The values are not given in the text fig. 3 fig. 4.
• Integration. Pick and place runs complete in simulation, and the robot avoids the repair area and keeps pedestrian distance, as described in words §5.5 fig. 5 fig. 6. The paper states the average instruction-to-task accuracy as 90% §5.5. Table 3 lists the integration checks in words; the "Task Completion" row has no entry tab. 3.

Table 3 is a qualitative integration summary with three rows tab. 3. Its task-completion row has no entry. The other two rows state, in words, that the robot kept clear of the repair area and of pedestrians, and that the grid updates matched the instructions. No counts are given.

Paper vs code

No official code.

The paper gives no code link, project page or repository, and the arXiv metadata has no comment field that names one. I searched GitHub for "DCIP", "DCIP instruction planning", "LLM path planning occupancy grid instructional", "LLM husky ur3 gazebo", "xuesu xiao" (users and repositories), "pranav doma navigation" and "aliasghar arab". None returned a repository from the authors.

Pitfalls

• The search algorithm is not named. DCIP's path search over the grid is never described. The path cost definition (sum of node costs plus zone costs) suggests a cost-based graph search, and A* is the only search named, and it is used only as the baseline §5.1.1. An implementer must choose the planner and the cost model.
• Cost values are missing. C_modify, C_high and the zone costs are symbols only §4.2 §4.3 §5.1.1. Path cost in tab. 2 depends on them, so the numbers cannot be reproduced.
• Cost columns are not like for like. DCIP path costs include zone weights §5.1.1. The A* path cost equals its path length (177.0 against 177) tab. 2, which suggests the baseline uses no zone weights, but the paper does not say.
• The LLM is a black box. No prompt, output schema, parser, temperature or checkpoint size is given §5.1. Only the model family names are reported. Without the prompt, the mapping from instruction to actions cannot be reproduced.
• Action names disagree. §4.1 lists RESET_MAP and AVOID_AREAS as examples, while §4.3 uses SET_GOAL and MODIFY_COST for the same kinds of effect §4.1 §4.3. Use one name set and say which.
• Obstacle set is undefined. MODIFY_COST changes "obstacles", but the paper does not say how the set is formed from semantic landmarks or from the grid §4.3 §4.4. The grid is binary in the problem statement §3, yet the method writes cost values into it §4.2 §4.3. The grid's data type, and whether it stores costs or occupancy, is not stated.
• Loop termination and failure cases are not described. Algorithm 1 repeats "while task not completed" with no completion test and no failure branch alg. 1.
• Latency is not measured. The abstract claims value in "resource-limited settings" [abstract], but no LLM latency, hardware or energy is reported. Search time in tab. 2 is execution duration of the search §5.1.1. The paper does not say whether LLM calls are inside it.
• Table 1 denominators vary. The percentages equal fractions with denominators of 7, 14, 28 and 35 (for example 28.57 = 2/7, 89.28 = 25/28, 91.42 = 32/35). The number of test instructions per cell is not stated, so the cells may not be comparable.
• Text and table disagree in places.
  • The text says Mistral is strong in Navigate Quickly §5.1. Its Navigate Quickly row in tab. 1 is its lowest on all three metrics (28.57, 42.85, 14.28).
  • The text says Llama3 is best in every strategy §5.1. In Navigate Quickly, Llama3.1 has higher completeness (71.42 against 64.28).
  • The text says Llama3.1 "lagged behind" §5.1. Its Balance row in tab. 1 is above Mistral's on all three metrics.
• Headline accuracy is inconsistent. §5.5 gives an average of 90%, while the conclusion says "over 90%" for instruction parsing §6. The paper does not define instruction-to-task accuracy or the number of instructions scored.
• Figure caption. The caption of the place-phase figure says "pick phase" fig. 6. Treat the phase label as unconfirmed.
• Real robot not tested. A real-robot figure appears in the source but is commented out §5.4. All results are simulated.
• Introduction citations are unclear. The text says DCIP is combined with MPC and DWA and cites LLM-Planner and NavCoT for that §1. The paper does not describe any MPC or DWA controller in the method.

Lineage

• Builds on: none named as the base method. The Problem Statement names A* and RRT* as the classic planners the work addresses §3.
• Compared against: A* only, on the same grid tab. 2. The introduction names BEVBert, CLIP-NAV, InstructNav, LLM-Planner and NavCoT as related LLM-based navigation work §1 §2. None is compared in experiments.
• Superseded by: not known from the wiki content.