Source-linked AI summary
Concurrent Semantic Search and Mission Execution for LTL Missions in Unknown Environments
Fernando Salanova Gaspar, David Morilla Cabello, Cristian Mahulea Poleuca, Eduardo Montijano Muñoz
TL;DR
LTLf missions in unknown environments require finding relevant objects while preserving the ability to complete temporally constrained tasks. This paper interleaves task-driven semantic search and mission execution in an adaptive waypoint planner. In photorealistic indoor experiments, it reports higher success in nearly every mission type, especially complex ones, with efficient paths and less environment explored.
Problem
Existing approaches separate exploration from mission execution, while myopic advancement can lead to mission-blocking states when required objects remain unseen.
Source: §I · p. 1Method
An adaptive planner combines an online VLM-built metric-semantic scene graph with a mission DFA to select and order waypoints for information gathering and mission advancement.
Source: §I · p. 2, D. Planning for exploration & mission… · p. 5Results
The method achieves the highest success rate for almost every mission type, especially complex ones, while producing efficient paths and exploring the least environment in those missions.
Source: 1) Baseline comparison · p. 7Takeaways & Limitations
Interleaving exploration and execution is associated with improved efficiency in complex missions, while combining semantic guidance with mission information reduces the observed environment.
Source: 1) Baseline comparison · p. 7
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
LTL missions in unknown environments require finding relevant objects, but existing planning approaches separate exploration from execution or risk advancing myopically. The paper proposes interleaving mission-driven semantic search with mission execution.
I. INTRODUCTION
- Existing approaches separate exploration from mission execution, making exploration agnostic to the mission and requiring redundant navigation and revisits.Myopic advancement can also reach states from which the mission cannot be satisfied when a required object is absent.Source: §I · p. 1
- VLM-based semantic information can guide observations toward regions likely to advance the mission instead of requiring exhaustive exploration.VLMs can relate natural-language missions to object categories and use surrounding semantic context to identify likely regions.Source: §I · p. 1
- The method interleaves task-driven semantic search and mission execution, selecting waypoints that gather needed information while advancing satisfiable stages.It recomputes the plan as information arrives and considers remaining mission stages to avoid blocking states.Source: §I · p. 2
A. Temporal-logic planning in unknown environments
- Prior temporal-logic planning in unknown environments relaxes workspace knowledge, but these methods omit information gathering or use geometric exploration without semantic guidance.The cited approaches include replanning as maps change, task-progress guidance, and steering away from states that discard accepting behaviors.Source: A. Temporal-logic planning in unknown… · p. 2
B. Semantic exploration
Semantic exploration typically targets single objects, whereas temporally structured missions make an observation’s relevance depend on mission progress. The paper frames the problem as jointly exploring for mission objects and executing the mission non-myopically.
B. Semantic exploration
- Semantic exploration uses object and spatial-context evidence to reduce redundant navigation, but existing guided searches target single objects.The relevance of an observation is not fixed for a temporally structured mission.Source: B. Semantic exploration · p. 2
C. Exploring and executing a mission
- Separating exploration from execution can require revisiting, while planning over partial information must avoid steps that prevent later mission completion.Prior joint scoring of exploration and task actions is described as using domains unable to express order, avoidance, or disjunction.Source: C. Exploring and executing a mission · p. 2
III. PROBLEM FORMULATION
- Missions use natural-language object categories and temporal or logical constraints; object actions are assumed to be handled by low-level controllers.A proposition is true when the robot remains near its associated object for the required duration.Source: §III · p. 2
- The problem is to build one high-level plan that explores for mission-related objects and executes an LTLf mission efficiently without blocking future satisfaction.The objective is to address exploration and task execution simultaneously rather than as separate stages.Source: §III · p. 2
IV. METHODOLOGY
The method combines an online scene graph with a DFA tracking the LTLf mission to plan information gathering and mission advancement together. It updates an ordered waypoint plan as scene and mission information change.
IV. METHODOLOGY
- The method incrementally builds a metric-semantic scene graph and tracks mission state with a DFA, using both representations for task-driven search and non-myopic advancement.The planner seeks an ordered sequence of 2D high-level waypoints at each replanning stage.Source: §IV · pp. 2–3
- As scene information and mission state change, the ordered plan is updated to adapt to newly available information.The planning horizon includes what can be planned with information available at that stage.Source: §IV · p. 3
- The planner first selects relevant waypoints to maximize plan value, then weighs their values against travel cost to choose the next waypoint.The process repeats until the mission is satisfied or no feasible continuation remains.Source: §IV · p. 3, Figure 2 · p. 3
A. Scene representation
The scene representation combines geometry, object detections, and room categories to support navigation, mission execution, and targeted semantic exploration. A VLM supplies contextualized object and room information as the graph is built online.
A. Scene representation
- The scene graph is built incrementally by integrating metric and semantic information at each time step.It supports spatial and semantic awareness for navigation, proposition fulfillment, and targeted exploration.Source: A. Scene representation · p. 3
- A probabilistic occupancy grid provides free, occupied, and unknown cells for navigation, path computation, and identifying explored-space boundaries.Source: A. Scene representation · p. 3
- The VLM identifies mission object categories and related categories, then contextualizes keyframe detections with a suggested room, frame position, and confidence.Projected detections are stored as object prototypes in the metric map.Source: A. Scene representation · p. 3
- Each object prototype records its predicted class, 2D map position, VLM confidence, detection count, and room where it was seen.Nearby projected detections are fused by averaging positions, retaining maximum confidence, and incrementing observation count.Source: A. Scene representation · pp. 3–4
- Distance-clustered room categories form a third scene-graph layer, and mission or related categories identify regions for execution or semantic exploration.Source: A. Scene representation · p. 4
B. Deterministic Finite Automaton
The mission is tracked with an acyclic DFA whose states encode progress and whose accepting states mark satisfaction. Waypoints are sampled to support geometric exploration, semantic search, and mission advancement.
B. Deterministic Finite Automaton
- The mission formula is compiled into an acyclic DFA whose state changes according to which propositions hold, with accepting states marking mission satisfaction.Because proposition truth is not precisely known, it is estimated from the scene representation.Source: B. Deterministic Finite Automaton · p. 4
C. Waypoint definition
- Geometric exploration waypoints lie at frontiers between free and unknown space, while semantic waypoints target clusters of related objects or room centers.Related object categories within a radius are grouped, and the waypoint is placed at a confidence-weighted centroid oriented toward most cluster items.Source: C. Waypoint definition · p. 4
- When an object category tied to an outgoing transition from the current DFA state is identified, a waypoint beside it can advance the mission.The figure illustrates the fridge as a mission-advancement waypoint, a chair-and-TV cluster as semantic exploration for a later sofa target, and avoidance of a forbidden bed region.Source: C. Waypoint definition · p. 4, Figure 3 · p. 4
D. Planning for exploration & mission advancement
The planner values candidate waypoints for both exploration and mission progress, then balances their value against travel cost to choose an adaptive high-level plan.
Exploration value
- Semantic exploration value reflects the confidence evidence in a related-object cluster; room waypoints receive a constant value, while a visited cluster waypoint is zeroed if its target is not found.A single uncertain object contributes little, whereas several related objects make a cluster more informative for the mission.Source: D. Planning for exploration & mission… · p. 4
- Geometric and semantic exploration waypoints direct search toward areas likely to contain mission-relevant objects, with geometric frontiers assigned a low base value.The planner also considers how far each candidate waypoint is from the robot.Source: D. Planning for exploration & mission… · p. 4
Mission advancement value
- Mission-advancement waypoint value considers DFA continuations toward acceptance, using remaining transition distance and possible paths to account for deadlocks from unseen objects.The value is conservative when one waypoint can trigger multiple transitions: it takes the minimum value across the successor states.Source: D. Planning for exploration & mission… · p. 5
- Waypoint valuation is non-myopic because it reads the whole automaton, accounting for how much of the mission remains after reaching a waypoint.A waypoint can therefore be valued beyond the transition immediately ahead.Source: D. Planning for exploration & mission… · p. 5
Navigation cost and plan
- The planner builds a greedy waypoint order by balancing travel cost against waypoint value, including all candidate waypoints in the plan.Travel cost is the shortest free-path distance, biased by waypoint value, with γ translating value into distance.Source: D. Planning for exploration & mission… · p. 5
- The robot executes the first waypoint, then recomputes the plan from updated scene and mission information, so exploration and mission advancement proceed together.The same plan includes geometric exploration, semantic exploration, and mission-advancement waypoints.Source: D. Planning for exploration & mission… · p. 5
V. IMPLEMENTATION DETAILS
The implementation builds geometric and semantic maps from simulated robot sensing, monitors mission satisfaction on the map, and replans at 2 Hz.
Mapping
- The occupancy map uses slam toolbox at 0.05 m per cell, built from a 2D lidar with a 110° forward field of view and 4 m range.Source: §V · p. 5
Semantic layers
- RGB-D keyframes are analyzed by Qwen3.5-9B for household objects, bounding boxes, confidence, and room type; detections below 0.65 confidence are discarded.Keyframes are captured every 0.15 m or 10° and at most every 0.3 s; retained detections are projected using depth and merged with same-category instances within 2.5 m.Source: §V · p. 5
- Rooms group same-type keyframes within 3 m, and an object is assigned to the room containing the most samples within 2.5 m.Source: §V · p. 5
Mission monitoring and planning
- A proposition holds within 0.75 m of a matching instance after 5 s, while negated constraints are violated immediately on entering range; replanning runs at 2 Hz.The robot declares the mission infeasible when no frontier remains and bounded search over mapped categories finds no completion.Source: §V · p. 5
Values
- Waypoint values are normalized to [0, 1], and the value-to-distance influence is bounded at γ = 4 m; the same values are used across scenes and mission types without tuning.The frontier value is 0.1, related-room value is 0.4, and cluster value uses accumulated confidence with nref = 3; the penalty is β = 0.15/rmax and Λ = 50.Source: §V · p. 5
Platform
- The simulated platform is a TurtleBot in Gazebo Harmonic with ROS 2 Jazzy and Ubuntu 24.04, using a Kobuki base, Nav2, and an MPPI controller.The differential-drive base is limited to 0.6 m s−1 and 1.5 rad s−1.Source: §V · p. 5
VI. EXPERIMENTS SETUP
The experiments assess whether jointly reasoning about exploration and mission state, with task-driven semantic search, improves completion and plan efficiency.
VI. EXPERIMENTS SETUP
- The experiments assess whether joint reasoning about exploration and mission execution improves LTLf mission completion.Source: §VI · p. 5
- The evaluation also tests whether task-driven semantic search yields more efficient plans than separating exploration from execution.Source: §VI · p. 5
- A further comparison tests plan efficiency against considering only one step into the future.Source: §VI · p. 5
A. Setup
The evaluation uses photorealistic household reconstructions and compares planning strategies under shared perception and navigation components. It measures mission completion, efficiency, exploration effort, and failure causes.
A. Setup
- Each mission type has 36 episodes, for 180 total, across four scenes, formula variations, and initial poses; execution plans use estimated objects while success is checked against ground truth.The benchmark uses HM3D-Sem, which provides 36 photorealistic household reconstructions with annotated object categories.Source: A. Setup · pp. 5–6
B. Metrics
- Success rate measures accepted mission completion; time to satisfaction and distance measure efficiency, while coverage measures the explored environment.Failure categories distinguish missing mission objects, sequence violations, and activation of a negated proposition.Source: B. Metrics · p. 6
C. Baselines
- The comparison includes a known-map gold standard, exhaustive geometric exploration, one-target-at-a-time semantic search, greedy subtask selection, and Percep-LTL.Baselines share the scene graph and perception and navigation stacks, isolating differences in planning strategy.Source: C. Baselines · p. 6
D. Experiments
The experiments compare the proposed planner with exploration and mission-planning baselines and test components of the method. Across the benchmark, it performs best on success for almost every mission type, especially complex ones, while producing efficient paths with less coverage.
D. Experiments
- The ablations remove semantic hints or sweep waypoint-group values to assess mission-driven exploration and the balance between exploration and mission advancement.Without hints, exploration is frontier-based while the VLM still detects targets; Table III covers this ablation.Source: D. Experiments · p. 6, Table III · p. 7
1) Baseline comparison:
- In sequential missions, separating exploration from execution can violate mission ordering, while methods that consider the LTL mission throughout perform comparably.For single-object search, most methods perform comparably, with VLFM standing out as a method designed for object search.Source: 1) Baseline comparison · p. 7
- In avoidance and branching missions, split-stage baselines lose performance mainly through mission-restriction violations; most proposed-method failures involve object search and perception.Every method except the two non-myopic methods incurs sequence failures; the few avoidance failures are attributed to objects not yet registered in the scene graph.Source: 1) Baseline comparison · p. 7
- Our method has the highest success rate for almost every mission type, especially complex ones, and the most efficient paths in complex missions while exploring the least environment.Table II reports the benchmark results across five mission types.Source: 1) Baseline comparison · p. 7
2) Ablation:
The method combines semantic hints with mission reasoning to make information acquisition more effective and efficient, and its waypoint values favor mission propositions over semantic hints and frontiers. The conclusion reports higher success in complex missions and greater efficiency when the method’s components are combined.
2) Ablation:
- Semantic hints make information acquisition more effective and efficient; without them, missions with several required objects see lower success, longer times, and more travel.In object search, both guided and unguided variants always succeed, but guided search finds the target sooner.Source: 2) Ablation · p. 7
3) Sensitivity analysis:
- The proposed waypoint ordering values reaching a proposition above following a semantic hint, and a hint above a frontier.Reducing mission value increases coverage and lowers success; reducing semantic or geometric value mainly harms efficiency through longer trajectories.Source: 3) Sensitivity analysis · p. 7
VIII. CONCLUSIONS
- The combined method achieves higher success in the most complex missions and improves mission time and traversed distance efficiency.The conclusion reports that combined components give the best performance.Source: §VIII · p. 7
- In Fig. 4, ours reaches both objects in order and avoids the sofa, while the baselines explore longer, miss avoidance, or lack information about the next target.The caption reports that ours produces the shortest path.Source: Figure 4 · p. 8