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.