Planning complex missions in unknown environments requires robots to reason simultaneously about what they should do and what they still need to discover. Existing approaches for solving LTLf missions typically assume a known environment, or separate the exploration of the environment from the execution of the mission, while semantic exploration methods look for one target at a time and ignore the mission being executed. To fill this gap, our main contribution is an adaptive high-level planning method that interleaves a task-driven semantic search with the execution of the mission, advancing both in a non-myopic manner. Our method leverages two representations built online, a metric-semantic scene graph, built with a Vision Language Model (VLM), that provides the evidence needed to locate the objects the mission refers to, and the deterministic finite automaton (DFA) encoding the mission, that indicates which of them matter at each mission state. At every planning stage, our planner selects the waypoints that are most valuable for both the semantic search and the advancement of the mission, valuing them over the remaining mission stages in order to avoid blocking states. The selected waypoints are then ordered in a single high-level plan, which is recomputed as new information arrives. In photorealistic indoor environments over five mission types, our method completes more missions than the compared approaches while having to cover less of the environment, and it does so with shorter paths and complying with the restrictions imposed by the mission.
Figures & tables
Fig. 1 : We address the problem of solving LTLf missions in unknown environments, which requires exploring the scene to find the objects the mission refers to. Our adaptive planning method interleaves both objectives, finding paths that gather the information the mission requires while advancing the stages that can already be satisfied.
Fig. 2 : Overview of the proposed method. The LTLf mission is compiled into a DFA that tracks its state and provides the categories related to the mission objects. The VLM build the scene graph, from which three kinds of waypoint are proposed, geometric exploration, semantic exploration and mission advancement. The planner returns the next waypoint of the path based on value and distance, repeating as the scene graph grows and the mission advances.
Fig. 3 : A planning stage for the mission above. The waypoints are sampled from the scene graph Sk and the mission state qk . The fridge is the proposition to reach, generating a mission advancement waypoint; the chair and the TV are related to the sofa, required later, so their cluster generates a semantic exploration waypoint; additional waypoints lie at the frontiers of the unexplored space. The bed is forbidden, and its region is avoided. The waypoint values are balanced with their relative distance to compute the high-level plan. As the robot advances, the waypoints and the plan are computed again.
Mission
LTLf formula
Object search
Fℓ5a
Sequential
F(ℓ5a∧F(ℓ5b∧Fℓ5c))
Avoidance
F(ℓ5a∧Fℓ5b)∧G¬ℓ0c
Conjunctive
F(ℓ5a∧Fℓ5b)∧F(ℓ5c∧Fℓ5d)
Disjunctive
(F(ℓ5a∧Fℓ5b)∧G¬ℓ0c)∨(F(ℓ5c∧Fℓ5d)∧G¬ℓ0a)
TABLE I : LTLf mission families used in the experiments.
Outcome
Error analysis ↓
Method
SR ↑
TTS ↓
Dist. ↓
Cov ↓
Expl.
Seq.
Avoid.
Object search
Known map [ 12 ]
100
39 ± 12
8.2 ± 0.9
—
—
—
—
FUEL + P. [ 20 ]
63.9
338 ± 52
53.2 ± 5.2
93.0
13
—
—
VLFM + P. [ 11 ]
83.3
64 ± 16
26.4 ± 6.2
46.1
6
—
—
Greedy ST [ 27 ]
75.0
86 ± 12
27.3 ± 5.6
56.8
9
—
—
Percep-LTL [ 5 ]
83.3
100 ± 11
29.4 ± 7.7
62.0
6
—
—
TABLE II : Results of the benchmark including different mission types. Among the compared methods, the best value is shaded in green and the second best in blue . Known-map ( grey ) is the reference gold-standard. TTS and Path are reported as mean ± standard deviation across episodes. SR and Cov are %, TTS are seconds, and Dist. are meters.
Fig. 4 : VLFM + P. [ 11 ] explores until all the objects are found, which lengthens the path and violates a restriction while exploring. Percep-LTL [ 5 ] also explores first, and the lack of semantic guidance induces an avoidance error. Greedy ST [ 27 ] reaches the first object without any information about the next one. Ours reaches both in order and keeps clear of the sofa, as the semantic guidance provides early evidence of the second target and yields the shortest path.
Mission
SR (%)
TTS (s)
Dist. (m)
Cov (%)
Ours
Obj. search
100.0
102.1 ± 12.4
22.5 ± 4.8
44.3
Conj. + avoid
80.0
200.9 ± 18.6
46.5 ± 7.2
67.7
Sequential
60.0
291.4 ± 22.7
65.8 ± 9.4
82.0
No hints
Obj. search
100.0
177.4 ± 21.2
33.5 ± 7.6
69.8
Conj. + avoid
53.3
357.1 ± 34.5
62.4 ± 10.1
94.2
Sequential
33.3
439.8 ± 40.3
82.8 ± 11.7
98.5
TABLE III: Ablation of the semantic hints. No hints disables the language model and builds no semantic waypoints, leaving pure frontier exploration, the VLM still detects targets. Fifteen episodes per mission type over five scenes.
Group
v
SR (%)
TTS (s)
Dist. (m)
Cov (%)
Tuned
—
75.0
234.9 ± 22.1
47.6 ± 6.3
68.3
Mission
0.00
50.0
389.4 ± 35.8
59.6 ± 7.4
95.3
0.25
58.3
359.9 ± 31.2
57.2 ± 8.2
91.2
0.50
66.7
288.7 ± 27.5
52.3 ± 6.8
77.6
0.75
75.0
255.6 ± 22.4
49.1 ± 6.2
71.5
Semantic
0.00
75.0
422.1 ± 42.7
61.9 ± 8.1
96.2
TABLE IV: Value sensitivity. Each group is swept while the others stay frozen. The tuned operating point is given for reference. Twelve episodes of the nested sequential mission, over four scenes.
Coordinating multi-robot systems (MRS) to search in unknown environments is particularly challenging for tasks that require semantic reasoning beyond geometric exploration. Classical coordination strategies rely on frontier coverage or information gain and cannot incorporate high-level task intent, such as searching for objects associated with specific room types. We propose \textit{Semantic Area Graph Reasoning} (SAGR), a hierarchical framework that enables Large Language Models (LLMs) to coordinate multi-robot exploration and semantic search through a structured semantic-topological abstraction of the environment. SAGR incrementally constructs a semantic area graph from a semantic occupancy map, encoding room instances, connectivity, frontier availability, and robot states into a compact task-relevant representation for LLM reasoning. The LLM performs high-level semantic room assignment based on spatial structure and task context, while deterministic frontier planning and local navigation handle geometric execution within assigned rooms. Experiments on the Habitat-Matterport3D dataset across 100 scenarios show that SAGR remains competitive with state-of-the-art exploration methods while consistently improving semantic target search efficiency, with up to 18.8% in large environments. These results highlight the value of structured semantic abstractions as an effective interface between LLM-based reasoning and multi-robot coordination in complex indoor environments.
The integration of Large Language Model (LLM) reasoning principles into classical robot path planning represents a rapidly emerging research direction. In this paper, we propose a Semantic Risk-Aware Heuristic (SRAH) planner that encodes LLM-inspired cost functions penalising geometrically cluttered or high-risk zones into an A∗ search framework, augmented with closed-loop replanning upon dynamic obstacle detection. We evaluate SRAH against two established baselines Breadth-First Search (BFS) with replanning and a Greedy heuristic without replanning across 200 randomised trials in a 15×15 grid-world with 20% static obstacle density and stochastic dynamic obstacles. SRAH achieves a task success rate of 62.0%, outperforming BFS (56.5%) by 9.7% relative improvement and Greedy (4.0%) by a large margin. We further analyse the trade-off between planning overhead, path efficiency, and failure-recovery count, and demonstrate via an obstacle-density ablation that semantic cost shaping consistently improves navigation across environments of varying difficulty. Our results suggest that even lightweight, LLM-inspired heuristics provide measurable safety and robustness gains for autonomous robot navigation.
Long-horizon robot planning requires jointly reasoning over semantic task structure and geometric feasibility. To successfully execute a task, a robot must decompose goals, select task-relevant objects, and sequence actions, while ensuring that plans satisfy spatial constraints such as limited free space and object collisions. In this work, we propose APIVOT, a VLM-based planner that adaptively interleaves language and visual thoughts for long-horizon planning. APIVOT learns to leverage language for semantic reasoning, while using visual thoughts as imagined future states for internal verification of geometric feasibility. On long-horizon kitchen tasks, APIVOT outperforms general-purpose VLMs and prior planning frameworks, achieving the largest gains in spatially constrained settings. We find that APIVOT learns meaningful modality selection behavior, demonstrating that adaptive interleaving of vision-language thoughts improves both planning success and reasoning efficiency.