Task Coordination for Service Robots Based on Multiple Markov Decision Processes

Abstract

Markov Decision Processes (MDPs) provide a principled framework for planing under uncertainty. However, in general they assume a single action per decision epoch. In service robot applications, multiple tasks are required simultaneously, such as navigation, localization and interaction. We have developed a novel framework based on functional decomposition that divides a complex problem into several sub-problems. Each sub-problem is defined as an MDP and solved independently, and their individual policies are combined to obtain a global policy. In contrast to most previous approaches for hierarchical MDPs, in our approach all the MDPs work in parallel, so we obtain a reactive system based on a decision theoretic framework. We initially solved each MDP independently and combined their policies assuming no conflicts. Then we defined two kinds of conflicts, resource and behavior conflicts, and proposed solutions for both. The first kind of conflict is solved off-line using a two phase process which guarantees a near-optimal global policy. Behavior conflicts are solved on-line based on a set of restrictions specified by the user, and a constraint satisfaction module that selects the action set with higher expected utility. We have used these methods for task coordination in service robots, and present experimental results for a messenger robot.