Abstract
We propose a human-supervised control synthesis method for a stochastic Dubins vehicle such that the probability of satisfying a specification given as a formula in a fragment of Probabilistic Computational Tree Logic (PCTL) over a set of environmental properties is maximized. Under some mild assumptions, we construct a finite approximation for the motion of the vehicle in the form of a tree-structured Markov Decision Process (MDP). We introduce an efficient algorithm, which exploits the tree structure of the MDP, for synthesizing a control policy that maximizes the probability of satisfaction. For the proposed PCTL fragment, we define the specification update rules that guarantee the increase (or decrease) of the satisfaction probability. We introduce an incremental algorithm for synthesizing an updated MDP control policy that reuses the initial solution. The initial specification can be updated, using the rules, until the supervisor is satisfied with both the updated specification and the corresponding satisfaction probability. We propose an offline and an online application of this method.
Introduction
In traditional robotics, motion planning often assumes deterministic execution or rigid constraints. However, real-world robots face significant uncertainty due to noisy actuators and imperfect sensors. Furthermore, mission specifications are often rigid; if a task is mathematically impossible or highly unlikely to succeed, standard systems may fail to provide any viable path. This paper addresses these challenges by introducing a "human-in-the-loop" framework. In this system, a robot reports its maximum probability of success for a given mission. If this probability is unacceptable, the human supervisor can "negotiate" by relaxing constraints or modifying the mission parameters to achieve a better balance between task difficulty and reliability.
Methods
The framework centers on a stochastic Dubins vehicle model, which accounts for random noise in steering. To manage the complexity of motion planning under uncertainty, the authors employ several key technical strategies:
Tree-Structured MDP
The robot's possible movements and associated noise are discretized into a Markov Decision Process (MDP). By structuring this MDP as a tree (avoiding cycles), the authors significantly simplify the computational requirements for policy synthesis.
Formal Logic and Policy Synthesis
Specifications are defined using a specific fragment of Probabilistic Computational Tree Logic (PCTL), allowing for complex behaviors like sequential goals and obstacle avoidance. The tree structure allows for a fast recursive algorithm to find optimal control strategies, bypassing the heavy linear programming typically required for MDPs.
Incremental Updates and Negotiation
A core contribution is the set of "specification update rules." These rules allow a human to modify the mission—for instance, by adding a destination or removing a restriction—in a way that is mathematically guaranteed to shift the success probability in a predictable direction. An incremental algorithm reuses previous solutions to calculate new optimal paths in seconds.
Case Study and Results
The approach was evaluated through a simulated case study involving a robot navigating an environment with various regions of interest, including pick-up zones, test areas, and unsafe regions.
Performance Metrics
In a test environment with approximately 45,000 states, the system demonstrated high efficiency:
- Initial Synthesis: The first control policy was generated in 23 seconds.
- Negotiation Speed: Incremental updates for modified missions were completed in 6 to 11 seconds.
- Reliability: Simulations confirmed that the calculated success probabilities serve as a safe lower bound. For example, a predicted 68% success rate resulted in an actual 74% success rate across 50 sample runs.
Conclusion
This research presents a viable path toward interactive robot supervision. By exploiting the structure of the motion model and formal logic, the authors enable real-time negotiation between humans and autonomous systems. While currently limited to tree-structured MDPs and a specific PCTL fragment, future work aims to extend this to higher-dimensional models like quadrotors and validate the system on physical hardware.
Summary updated