Mind-Theoretic Planning

The MTP system frames the problem of mind-theoretic reasoning as a planning problem with mixed observability. A predictive forward model of others’ behavior is computed by creating a set of Mental State Situations (MSS), each composed of stacks of Markov Decision Process (MDP) models whose solutions provide approximations of anticipated rational actions and reactions of that agent. This forward model, in addition to a perceptual-range limiting observation function, is combined into a Partially Observable MDP (POMDP). The presented MTP approach increases computational efficiency by taking advantage of approximation methods offered by a novel POMDP solver B3RTDP as well as leveraging value functions at various levels of the MSS as heuristics for value functions at higher levels. This work was supported by an ONR MURI 6 Award N00014-07-1-0749

For the purpose of creating an efficient MTP system, a novel general-purpose online POMDP solver B3RTDP was developed; this planner extends the Real-Time Dynamic Programming (RTDP) approach to solving POMDPs. By using a bounded value function representation, we are able to apply a novel approach to pruning the belief-action search graph and maintain a Convergence Frontier, a novel mechanism for taking advantage of early action convergence, which can greatly improve RTDP search time.

We developed an online video game for the purpose of evaluating the MTP system by having people complete tasks in a virtual environment with a simulated robotic assistant. A human subject study was performed to assess both the objective behavioral differences in performance of the human-robot teams, as well as the subjective attitudinal differences in how people perceived agents with varying MTP capabilities. Study results show that providing agents with mind-theoretic capabilities can significantly improve the efficiency of human-robot teamwork in certain domains and suggest that it may also positively influence humans’ subjective perception of their robotic teammates