Dai et al. plan navigation missions given in natural language (“visit the bathroom on floor 0 and avoid the sink, then sit on a chair in the dining room”) over a known scene graph, and keep an optimality guarantee even though an LLM is in the loop. GPT-4 first maps the mission onto unique IDs in a compact YAML “attribute hierarchy” of floors, rooms and objects, then writes a co-safe LTL formula in prefix notation; a syntax and co-safety checker sends it back for correction, and a human rephrases the mission if the retries run out. Spot turns the formula into an automaton, and the planner searches the product of scene graph nodes and automaton states with AMRA*, a multi-resolution, multi-heuristic A* with levels for occupancy, objects, rooms and floors. Two heuristics guide it: a consistent LTL heuristic (proved in the paper) on the anchor level, which keeps the final path optimal, and an LLM heuristic that turns GPT-4’s suggested sequence of moves between rooms and objects into a cost estimate, which may be inadmissible but speeds up the search.
Findings
- Tested on three Gibson scenes from the 3D Scene Graph dataset (Allensville with 1 floor, Benevolence and Collierville with 3), 5 missions per scene and 5 start positions per mission.
- On one Benevolence mission, LLM guidance at every level returns a first feasible path in 0.0007 s against 1.12 s for plain A* on the occupancy level, but that first path costs 1.38 times the optimum. Time to the optimal path is 8.9 s against 11.8 s for A* and 24.3 s for the hierarchy without LLM guidance.
- Averaged per scene, the full LLM setup finds a first path in 0.32 s on Benevolence and 0.009 s on Collierville (A*: 1.33 s and 1.19 s), and the optimal path in 11.82 s and 5.48 s (A*: 14.22 s and 7.04 s). On the single-floor Allensville, plain A* wins on all three measures (0.15 s, 1.08, 3.23 s against 0.24 s, 1.69, 3.50 s).
- Adding the LLM heuristic to any level cuts node expansions, and adding it to more levels helps more.
- The LLM heuristic is queried offline and cached, because query latency and rate limits make online calls impractical inside A*.
Limits
- The scene graph is known, complete and static. Missions are navigation only (reach, visit, avoid); there are no state changes such as opening a door or picking something up.
- The first paths under LLM guidance can be 24% to 69% more expensive than optimal (the per-scene averages); speed comes from trusting the LLM, and optimality comes later from the anytime search.
- The paper does not report how often the NL-to-LTL translation is right across many missions, and the human-in-the-loop fallback is part of the pipeline.
- The heuristic proof needs a cost that satisfies the triangle inequality, which holds for path length but not obviously for costs like risk or energy in currents.
Relevance
It is a formal counterpart to SayPlan: the LLM is allowed to be wrong, and a consistent heuristic stops it from making the final plan worse. That split (fast, untrusted guidance from a model; guarantees from a checker) could carry over to robust robotics, for example when the “untrusted” input is another robot’s map. See language-grounded-planning, 3d-scene-graphs, and the symbolic planning baselines in Taskography.