Collaborative Rover-copter Path Planning and Exploration with Temporal Logic Specifications Based on Bayesian Update Under Uncertain Environments

Kazumune Hashimoto, Natsuko Tsumagari, Toshimitsu Ushio

Introduction

Robotic missions in unknown or hazardous environments—such as planetary exploration, search and rescue, or disaster response—require more than simple point-to-point navigation. These missions often involve complex, high-level requirements that must be satisfied sequentially or conditionally. For instance, a robot might be tasked to "visit target A, then visit B, while avoiding hazardous zone C at all times." Such requirements are formally expressed using Linear Temporal Logic (LTL).

However, planning for LTL specifications in uncertain environments presents a significant computational challenge. Traditional methods, such as Partially Observable Markov Decision Processes (POMDPs), often suffer from the "curse of dimensionality," where the state space grows exponentially with the size of the map, making real-time onboard computation impossible for large-scale missions. This paper introduces a collaborative rover-copter framework designed to overcome these limitations through efficient scouting and a novel planning architecture.

Problem Statement

The primary challenge addressed is the efficient execution of LTL-constrained missions in environments where the map is initially unknown. The system must manage two types of uncertainty: the robot's lack of knowledge about environmental properties (e.g., whether a cell contains an obstacle or a target) and the computational complexity of updating plans as new information is gathered. Existing approaches that include continuous belief states within the core planning MDP quickly become computationally infeasible as the environment scales.

Proposed Methodology

The authors propose a heterogeneous multi-robot team consisting of a fast-moving aerial "copter" and a mission-focused ground "rover." The copter acts as a scout, reducing environmental uncertainty to inform the rover's path planning.

1. Environmental Beliefs and Bayesian Updates

The environment is modeled as a grid where each cell has specific properties (atomic propositions). Instead of a binary "occupied or free" map, the system maintains a belief—a probability between 0 and 1—for every property in every cell. As the robots traverse the environment, they use Bernoulli-type sensor models to perform Bayesian updates. If the copter’s sensors detect an obstacle, the belief for that cell shifts toward 1; if clear ground is observed, it moves toward 0.

2. The Product Belief MDP

The core technical innovation is the Product Belief MDP. To plan the rover's path, the framework combines the rover's motion model with a Finite State Automaton (FSA) that represents the LTL mission logic. Crucially, the authors decouple the continuous belief values from the core state space. By treating the beliefs as parameters that influence transition probabilities rather than as state variables themselves, the system avoids the exponential complexity growth typical of POMDPs.

3. Relevance-Aware Exploration

The copter’s movement is guided by an acquisition function that balances two critical factors:

  • Entropy: The level of uncertainty in a specific area.
  • Reachability: The likelihood that the rover will need to pass through that area to satisfy its LTL mission.

This "scouting the future" approach ensures the copter prioritizes areas that are both unknown and mission-critical, preventing the waste of battery and time on irrelevant sections of the map.

Experimental Evaluation

The framework was evaluated using simulated environments, including a 10x10 grid with multiple targets and obstacles. The study compared the proposed method against existing state-of-the-art LTL planning approaches.

Key Results

  • Computational Efficiency: In a 15-cell benchmark, the proposed method synthesized a policy in just 0.22 seconds, whereas the previous state-of-the-art required 86.02 seconds.
  • Scalability: Previous methods often encountered memory overflows on maps larger than 12 cells. In contrast, the new framework successfully handled a 100-cell map in approximately 20 seconds, demonstrating a shift from exponential to polynomial complexity.
  • Mission Success: The researchers compared "Global Selection" (copter identifies the most critical point across the entire map) with a "Local Greedy" approach. Global Selection achieved a 71% mission completion rate, significantly higher than the 62% achieved by the local approach within the same constraints.
  • Convergence: The authors provided mathematical proof that environmental beliefs are guaranteed to converge to the ground truth given sufficient exploration time.

Discussion and Future Work

The separation of concerns—where the copter gathers information and the rover executes the mission—allows for a highly optimized system that can handle complex logic in real-time. By utilizing reachability beliefs, the copter mimics human scouting behavior, identifying potential "deal-breakers" (like blocked paths) before the rover commits to a route.

Despite these successes, the framework currently lacks "hard" safety guarantees during the learning phase, meaning there is a non-zero risk of collision before the map is fully known. Additionally, the current model uses a simplified Bernoulli sensor model. Future research will focus on concurrent coordination—allowing both robots to move and update plans simultaneously—and integrating more complex sensor models to account for real-world occlusions and computer vision limitations.

Summary updated

Abstract

This article investigates a collaborative rover-copter path planning and exploration with temporal logic specifications under uncertain environments. The objective of the rover is to complete a mission expressed by a syntactically co-safe linear temporal logic (scLTL) formula, while the objective of the copter is to actively explore the environment and reduce its uncertainties, aiming at assisting the rover and enhancing the efficiency of the mission completion. To formalize our approach, we first capture the environmental uncertainties by environmental beliefs of the atomic propositions, under an assumption that it is unknown which properties (or, atomic propositions) are satisfied in each area of the environment. The environmental beliefs of the atomic propositions are updated according to the Bayes rule based on the Bernoulli-type sensor measurements provided by both the rover and the copter. Then, the optimal policy for the rover is synthesized by maximizing a belief of the satisfaction of the scLTL formula through an implementation of an automata-based model checking. An exploration policy for the copter is then synthesized by employing the notion of an entropy that is evaluated based on the environmental beliefs of the atomic propositions, and a path that the rover intends to follow according to the optimal policy. As such, the copter can actively explore regions whose uncertainties are high and that are relevant to the mission completion. Finally, some numerical examples illustrate the effectiveness of the proposed approach.
BibTeX
@article{hashimoto2022collaborative,
  author = {Kazumune Hashimoto and Natsuko Tsumagari and Toshimitsu Ushio},
  title = {{Collaborative Rover-copter Path Planning and Exploration with Temporal Logic Specifications Based on Bayesian Update Under Uncertain Environments}},
  journal = {ACM Trans. Cyber Phys. Syst.},
  year = {2022},
  doi = {10.1145/3470453},
}
Figure