Grid2Guide: A* Enabled Small Language Model for Indoor Navigation

The gist The research presents Grid2Guide, a hybrid navigation framework that combines the A search algorithm with a Small Language Model (SLM) to generate clear, human-readable route instructions.

How it works

Grid2Guide is a five-stage pipeline that transforms a static floorplan image into fluent, human-readable directional instructions From the user’s perspective, the system requires only two inputs: the origin and the destination on the map The approach consists of (i) Map Preprocessing and Grid Generation, (ii) Graph Encoding, (iii) A search with Diagonal Moves, (iv) Path Compression, and (v) SLM-Based Instruction Generation.

1. Map Preprocessing and Grid Generation

The initial objective is to generate an obstacle-aware map from the provided floorplan image This is achieved by converting the image into a binary occupancy grid, classifying each pixel as either walkable or blocked using standard image thresholding and polygon-masking techniques. The mask encodes walkable versus obstructed regions in the map. For locations comprising multiple floors, a separate occupancy matrix is constructed for each level To enable vertical traversal, portal nodes are manually defined at the locations of the connecting points (i.e., staircases, elevators, or escalators).

2. Graph Encoding

In our implicit graph representation, every free cell Gi,j = 1 becomes a node It is connected to its eight neighboring cells (i + ∆i, j + ∆j) for ∆i, ∆j ∈ (−1, 0, 1)⋃(0, 0). This 8-way connectivity is proposed to ensure smooth, diagonal shortcuts around sharp corners in the grid map. The movement cost is assigned such that c(∆i, ∆j) = 1 for orthogonal moves and c(∆i, ∆j) = √2 for diagonal moves.

3. A Search with Diagonal Moves

A search algorithm augmented with 8-way (diagonal) movement is employed to compute the shortest path between the specified start and goal coordinates. The A search maintains three quantities for each free cell (i, j): Cost-to-Come, g(i, j), Heuristic Estimate, h(i, j), and Total Score, f(i, j) = a(i, j) + h(i, j). The heuristic used is the Chebyshev distance h((i, j),(it, jt)) = max(i − it, j − jt), which perfectly aligns with our mixed-cost model.

4. Path Compression

The raw output of the A search algorithm is a long sequence of grid-cell coordinates. This verbose list is transformed into concise movement commands via a three-stage compression pipeline:

** Stage 1 - Vectorization:**

The displacement between successive cells yields one of the eight possible unit vectors, mapped to a compass code.

** Stage 2 - Run-Length Encoding:**

Consecutive identical codes are merged into tuples (dir, n), where n is the count of repeated steps.

** Stage 3 - Diagonal Collapse:**

Adjacent single-step pairs are replaced with a single diagonal entry to avoid zig-zag walking patterns.

5. SLM-Based Instruction Generation

The SLM is engaged in the last step to transform terse commands into natural, numbered directions. The SLM is instruction-tuned with a small dataset and uses a system prompt to reduce model hallucination. The prompt incorporates both the terse outputs from the A search and cost for navigation.

Evaluation Outcomes

The approach was evaluated against a baseline method introduced by Coffrini et al. (25): This framework relies on LLM, specifically ChatGPT, to generate instructions from preprocessed floor plan images. While this method demonstrated a single-instruction-level accuracy of around 86%, it suffers from significant computational overhead with an average processing time of approximately 4-5 minutes per query. In contrast, the Grid2Guide approach achieved 100% accuracy across all experimented maps because it integrates A search with an SLM, leveraging the A search algorithm for accurate path computation while reserving the machine learning model solely for the generation of natural language instructions. The modular design decouples image processing and path planning from language generation, ensuring reasoning over spatial structures is handled algorithmically rather than probabilistically.

Conclusion

This paper introduces a new A search enabled SLM indoor navigation approach for personal navigation using handheld devices. By converting standard architectural floor-plan images into lightweight binary occupancy grids, the need for heavy image processing inside the LLM is eliminated. The 8-way A search implementation computes optimal routes in a few milliseconds, ensuring real-time response on commodity hardware. A language model is only utilized for converting the terse texts into conversational, human-understandable output. Future work should involve finding optimized navigation instructions dynamically. The text outputs can be easily converted to speech instructions, providing directional guidance to people with visual impairments.

Authors Contribution

Md. Wasiul Haque, Sagar Dasgupta: conceptualization, methodology, coding, data collection, data analysis, and writing – original draft; Mizanur Rahman: conceptualization, methodology, writing – original draft.

Acknowledgements

This work is based upon the work supported by the National Science Foundation (NSF) (Award 2340456).

References

The paper cites various works including Bosch and Gharaveis (25), Guerreiro et al. (19), Belir and Onder (13), Jeong et al. (18), Iftikhar et al. (21), Coffrini et al. (25) etc., supporting the context of indoor navigation challenges and existing solutions. The specific references cited are numerous, including those for SLAM platforms like IndoorAtlas and Quuppa (19), as well as path planning algorithms like A search (13), Dijkstra algorithm (25), and various LLM advancements such as FLAN-T5 and TinyLlama (24). The paper's methodology draws on concepts from geometric algorithms, bionic algorithms, and instruction-tuned transformer models to achieve its goal. The evaluation compares the proposed system against the Coffrini et al. (25) baseline to demonstrate superior accuracy and performance in real-time scenarios. The paper's findings confirm that offloading deterministic path planning to A search and limiting the machine learning model’s role to lightweight text formatting delivers 100% route accuracy and true real-time performance. The combination of these techniques enables a scalable, cost-effective solution for indoor navigation support on mobile-class hardware. The work is supported by the National Science Foundation (NSF) under Award 2340456. The paper's structure follows a standard scientific format, including an introduction, literature review, method, evaluation, and conclusion. The authors acknowledge the use of ChatGPT for rephrasing parts of their writing for editorial purposes.

1. textbf Processing Bottleneck Mitigation via SLM Offloading: The system avoids resource-intensive LLM reasoning by utilizing an SLM solely to generate human-readable instructions from terse navigation instructions, which minimizes the risk of probabilistic navigation errors while maintaining natural, intuitive guidance.

2. textbf Deterministic Path Planning for Real-Time Performance: By offloading geometric reasoning to the A∗ algorithm, the pipeline eliminates the need for a machine learning model to directly process the image or infer spatial relationships, ensuring that A is fully deterministic and produces routes in just a few milliseconds.

3. textbf Scalable Multi-Floor Navigation: The incorporation of portal nodes enables seamless traversal across multiple levels, addressing the limitation that no prior indoor navigation framework has demonstrated lightweight multi-floor path planning combined with natural language instruction generation.

4. textbf Robust Map Interpretation via Majority Voting: The map preprocessing step uses a majority-voting strategy to classify cells as walkable or blocked based on pixel density (if more than half of its pixels are blocked by any obstacles in the actual map, we mark the cell blocked (0); otherwise, we mark it free (1)), which handles noisy edges or slight misalignments in the hand-drawn mask.

5. textbf Optimized Path Generation via Diagonal Collapse: The path compression stage addresses unrealistic movement by replacing adjacent single-step pairs with a single diagonal entry (Whenever found, we replaced those with a single diagonal entry such as (SE, 1)), improving the human-understandable navigation instruction quality compared to paths relying only on orthogonal moves.

Reliable indoor navigation remains a significant challenge in complex environments, particularly where external positioning signals and dedicated infrastructures are unavailable. This research presents Grid2Guide, a hybrid navigation framework that combines the A* search algorithm with a Small Language Model (SLM) to generate clear, human-readable route instructions. The framework first conducts a binary occupancy matrix from a given indoor map. Using this matrix, the A* algorithm computes the optimal path between origin and destination, producing concise textual navigation steps. These steps are then transformed into natural language instructions by the SLM, enhancing interpretability for end users. Experimental evaluations across various indoor scenarios demonstrate the method's effectiveness in producing accurate and timely navigation guidance. The results validate the proposed approach as a lightweight, infrastructure-free solution for real-time indoor navigation support.