Augmenting Markov Decision Processes with Advising

Loïs Vanhée, Laurent Jeanpierre, Abdel-Illah MouaddibAAAI 2019 · DOI

Introduction

Standard Markov Decision Processes (MDPs) are foundational for robotic planning under uncertainty. However, they often fail in complex, real-world environments where transition models are incomplete or environmental hazards—such as slippery surfaces or security threats—are not pre-mapped. Existing approaches to human-robot interaction generally fall into two categories: Mixed-Initiative Planning Systems (MIPS), which require high operator workload for constant plan validation, and Advice-Sensitive Reinforcement Learning (ASRL), which suffers from long training times and difficulty incorporating high-level semantic advice. This paper introduces Advice-MDPs, a framework that allows human operators to "nudge" robotic planning by marking states or actions with semantic advice, significantly reducing operator workload while maintaining autonomous performance.

The Advice-MDP Framework

The core contribution is the Advice-MDP formalism, which extends the standard MDP tuple $(S, A, T, R)$ by incorporating five categories of human-provided advice:

  • Goal (G): Target states for the robot to reach.
  • Forbidden (Sf) / Undesired (Su): States to be avoided, categorized by varying levels of priority.
  • Desired (Sd): Beneficial states that the robot should attempt to visit.
  • Forbidden Actions (Cπ): Context-specific actions that are off-limits in certain states.
The system architecture illustrates the flow from operator input via a GUI to the MDP Planner and final execution on the robot hardware.

To process this advice, the system transforms the Advice-MDP into a Multi-Objective MDP (MOMDP). Rather than optimizing a single scalar reward, the robot manages a vector of criteria. Decisions are made using a lexicographic ordering (LexDiff) and Ordered Weighted Regret (OWR) to prioritize safety (avoiding forbidden actions and states) while pursuing goals. A fast approximate value iteration algorithm ensures the system can complete a "sense-reason-act" loop in under two seconds, enabling responsive real-time operation.

Experimental Evaluation

The system was evaluated using NERVA mobile robots in two primary scenarios:

  1. Corridor Scenario: A standard navigation task designed to measure operator workload (OW).
  2. Hole Scenario: A "virtual hole" undetectable by the robot's base sensors was placed in the environment, necessitating human advice to prevent mission failure.

The Advice-MDP approach was benchmarked against Fully-Autonomous Systems (FAS), manual teleoperation, Action Pruning (ASRL), and Plan Revision (MIPS).

Results and Insights

The experimental results demonstrate that Advice-MDPs provide a superior balance between autonomy and human control. In the "Hole" scenario, where standard autonomous systems failed 100% of the time due to sensor limitations, Advice-MDPs achieved 81.3% effectiveness.

Comparison of path planning results: (left) hexagonal grid navigation, (middle) waypoint-based planning, and (right) path adjustment based on forbidden zone advice (red markers).

Key performance metrics include:

  • Workload Reduction: In the corridor experiment, the Operator-Workload for Advice-MDPs dropped to zero after initial setup, whereas teleoperation required constant engagement and MIPS required periodic plan revisions.
  • Efficiency: Advice-MDPs matched the speed of teleoperation while requiring significantly less human intervention time.
  • Learning Advantage: Compared to ASRL, which required over 100 operator checks to learn a simple constraint, the Advice-MDP system incorporated the same constraint immediately from a single piece of semantic advice.

Conclusion

Advice-MDPs offer a prescriptive rather than reactive approach to human-in-the-loop planning. By allowing operators to provide high-level semantic advice, the system reduces cognitive load and eliminates the need for expensive training phases. Future work aims to extend this framework to multi-robot coordination and integrate it with Partially Observable MDPs (POMDPs) to better handle sensor noise and environmental uncertainty.

Summary updated

BibTeX
@inproceedings{vanhee2019augmenting,
  author = {Loïs Vanhée and Laurent Jeanpierre and Abdel-Illah Mouaddib},
  title = {{Augmenting Markov Decision Processes with Advising}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012531},
}
Figure