TLDR: Grid2Guide is a new indoor navigation system that combines the A* search algorithm with a small language model (SLM). It converts floor plans into a simple grid, uses A* to find the fastest path, and then employs an SLM to turn these paths into clear, human-readable directions. This approach offers highly accurate, real-time navigation without needing expensive infrastructure, making it suitable for handheld devices.
Navigating complex indoor environments like airports, shopping malls, and hospitals can often be a confusing and time-consuming experience. Unlike outdoor spaces where GPS provides reliable guidance, indoor areas suffer from signal loss due to physical barriers, making traditional navigation systems ineffective. Current indoor navigation solutions often rely on expensive and hard-to-maintain infrastructure such as Wi-Fi fingerprinting or Bluetooth beacons, limiting their widespread adoption.
Recently, large language models (LLMs) like ChatGPT and Gemini have shown promise in interpreting natural language and even images, suggesting they could act as interactive indoor navigation assistants. However, directly processing floor plan images with LLMs is computationally intensive and slow, taking several minutes per query. This makes them impractical for real-time use on handheld devices, and their probabilistic nature can sometimes lead to inaccurate directions.
Introducing Grid2Guide: A Smart, Lightweight Solution
To overcome these challenges, researchers have developed Grid2Guide, a novel hybrid navigation framework. This system combines the efficiency of the A* search algorithm with the clarity of a Small Language Model (SLM) to provide accurate, real-time, and human-readable route instructions. The core idea is to offload the complex spatial reasoning to a fast, deterministic algorithm, and use the SLM only for generating user-friendly text.
How Grid2Guide Works
The Grid2Guide system operates in five main stages:
First, a given indoor map image is preprocessed and converted into a simple binary occupancy grid. This grid classifies each area as either walkable or blocked, creating a digital representation of the navigable space. This step is performed only once per map.
Next, this grid is encoded into a graph where each walkable cell becomes a node. The system allows for 8-way movement (including diagonal paths), assigning different costs to orthogonal and diagonal moves to ensure realistic pathfinding.
The A* search algorithm then takes over. Given an origin and a destination on the map, A* efficiently computes the optimal path. This algorithm is known for its speed and accuracy, guaranteeing the shortest path with minimal computational resources. It’s much faster than relying on an LLM to interpret the map directly.
Once the optimal path is found, it’s often a long sequence of grid coordinates. To make this manageable, a path compression technique is applied. This process condenses repetitive movements and zig-zag patterns into concise directional commands, like “Go East 5 steps” or “Go Southeast 2 steps.”
Finally, these terse, compressed commands are fed into a Small Language Model (SLM), specifically TinyLlama-1.1B in the experiments. The SLM, which has been instruction-tuned, transforms these commands into clear, numbered, and conversational walking instructions. For example, “Go East 3 steps Go North 1 step” becomes “1. Start by walking east for 3 steps. 2. Finally, walk north for 1 step and you will reach your destination.” This text-based transformation is lightweight and avoids the heavy image processing associated with larger LLMs.
Also Read:
- AI-Powered Indoor Wayfinding: Combining Camera Vision with Language Models
- SkillNav: Teaching AI to Navigate by Mastering Atomic Skills
Performance and Accuracy
Grid2Guide was rigorously tested on various indoor maps, including those of international airports and a large shopping center. The results were highly impressive. While previous LLM-based approaches struggled with accuracy (ranging from 62% to 82% success rates), Grid2Guide achieved a perfect 100% accuracy in generating optimal routes across all test cases. This is because the A* algorithm handles the precise pathfinding deterministically, removing the probabilistic errors of LLMs.
Furthermore, the system demonstrated remarkable speed. The A* search itself completed in milliseconds (under 5ms on average), and the entire process, including pathfinding and SLM-based instruction generation, took less than 20 seconds on average. This is a significant improvement over LLM-only methods, which often required 4-5 minutes per query, making Grid2Guide truly viable for real-time applications on standard handheld devices.
The modular design of Grid2Guide, separating spatial reasoning from language generation, ensures both high accuracy and efficient performance. This approach is also flexible, allowing for the use of any instruction-tuned SLM capable of local inference. Future developments could include integrating sensor outputs to dynamically update the occupancy grid, allowing the system to account for temporary obstacles like crowds or maintenance work. For more technical details, you can refer to the full research paper here.
