Turning an instruction such as “bring me something to drink from the kitchen” into a plan a robot can execute, using a map of the actual place. The map is usually a 3D scene graph, since its nodes and relations can be written out as text for a language model.
Approaches
- Paste the whole graph into the prompt. ConceptGraphs and FunGraph do this. It stops working once the graph is bigger than the context window.
- Let the LLM page through it. SayPlan starts from a collapsed graph and lets GPT-4 expand and contract nodes until it finds the relevant part. It finds the right subgraph in 86.7% of simple and 73.3% of complex queries; GPT-3.5 manages almost none. The fixed prompt alone takes about 3900 of 8192 tokens, and in the 300-room test every failure was a token overflow.
- Prune before planning. Taskography keeps the goal objects and everything linked to them, which is provably enough when the graph is correct. A classical planner that couldn’t finish in 24 hours on the full graph solved 72.86% of problems within 30 s on the pruned one. Pruning mattered more than the choice of planner.
- Compress while mapping. Clio keeps only what is informative about a task list given in advance.
- Keep a formal check around the LLM. In Dai and others, GPT-4 supplies a heuristic that may be wrong, and a consistent heuristic from a temporal-logic formulation keeps the final path optimal. First paths cost 1.24 to 1.69 times the optimum. The multi-robot system from MIT turns language into one PDDL goal per robot and hands those to a planner.
- Learn a policy on the graph. Ravichandran and others train a graph neural network to navigate over the scene graph. It does worse than a policy that only sees places once about 40% of the labels are wrong.
Assumptions
Every planner here assumes the graph is right. Taskography’s guarantee is for correct predicates. SayPlan’s simulator checks a plan against the same graph it was made from. Only Ravichandran’s paper measures what happens when labels are wrong, and the answer is that the learned policy falls apart.
Dai’s split, an untrusted proposer and a trusted checker, could extend from an LLM’s suggestions to a teammate’s map: use what the other robot says to guide the search, and only commit to what you can verify. That ties planning to robust robotics and runtime monitoring.
Questions
- What does a planner do when two robots’ graphs disagree about whether the door is open?
- How much of a plan should be re-checked when the scene changes under it (see dynamic scenes)?
- Most of these call a hosted LLM. What is the fallback when the link drops, underground or at a disaster site?
Related: open-vocabulary mapping, foundation models for robotics, multi-robot multimodal perception.