Abstract
In this work, we present a new planning formalism called Expectation-Aware planning for decision making with humans in the loop where the human's expectations about an agent may differ from the agent's own model. We show how this formulation allows agents to not only leverage existing strategies for handling model differences like explanations and explicability, but can also exhibit novel behaviors that are generated through the combination of these different strategies. Our formulation also reveals a deep connection to existing approaches in epistemic planning. Specifically, we show how we can leverage classical planning compilations for epistemic planning to solve Expectation-Aware planning problems. To the best of our knowledge, the proposed formulation is the first complete solution to planning with diverging user expectations that is amenable to a classical planning compilation while successfully combining previous works on explanation and explicability. We empirically show how our approach provides a computational advantage over our earlier approaches that rely on search in the space of models.
Introduction
Effective human-robot collaboration requires agents to account for the mental states of their human partners. A major hurdle is knowledge asymmetry, where a robot's internal model ($\mathcal{M}_R$) differs from the human's expectation of that model ($\mathcal{M}_H$). For instance, in search-and-rescue, a robot might know a path is blocked while the human commander does not. If the robot acts purely on its own knowledge, its behavior may seem suboptimal or invalid to the human. Historically, this has been addressed via either explanations (communicating model differences) or explicability (altering behavior to match human expectations). This paper proposes Expectation-Aware (EA) Planning to unify these strategies into a single, computationally efficient framework.
Expectation-Aware Planning Framework
The EA planning problem is defined by the divergence between the robot's model and the human's mental model. The goal is to generate a plan that is both valid in the real world and perceived as optimal by the human. Figure 3 demonstrates a scenario where the robot and human have conflicting information about the environment, such as the location of fires or debris, which leads to different expected paths.
Technical Approach: Compilation to Classical Planning
Rather than searching through the complex space of possible models, the authors compile the EA problem into a classical planning task. This is achieved by creating an augmented model ($\mathcal{M}_\Psi$) that incorporates:
- Meta-fluents: Variables tracking human beliefs (e.g., "The human believes the door is locked").
- Explanatory Actions: Communicative acts that update human beliefs.
- Epistemic Side Effects: Physical actions that implicitly update the human's model through observation (e.g., opening a door reveals it is unlocked).
This compilation allows the use of highly optimized classical planners and proves that solving these problems remains PSPACE-complete, no harder than standard planning.
Experimental Evaluation
The framework was evaluated on modified International Planning Competition (IPC) domains, including Blocksworld, Elevator, and Satellite. The researchers introduced random model differences to simulate human misconceptions.
As shown in the table above, the compilation method significantly outperforms the previous state-of-the-art model-space search. In the Elevator domain, runtime dropped from over 3300 seconds to under 60 seconds, while coverage improved across almost all domains. The framework successfully generated "Optimally Balanced Plans," finding the ideal trade-off between physical efficiency and communication effort.
Conclusion
Expectation-Aware planning provides a robust, efficient solution for generating explicable behavior and explanations. By unifying these strategies through classical planning compilation, robots can better navigate complex social and physical environments. Future research will focus on handling uncertainty in the human's mental model and extending the framework to stochastic settings.
Summary updated