We consider the problem of solving qualitative decentralized partially observable Markov decision processes (QDec-POMDPs) with deterministic actions. QDec-POMDPs model dynamic systems consisting of a collaborative team of agents acting under uncertainty and partial observability, attempting to reach a desirable goal state. They can be viewed as the multi-agent version of the contingent planning model. In this work, we extend the idea of factored planning from fully observable multi-agent planning to partial observability. Our method operates as follows: First, we simplify the multi-agent planning (MAP) problem by reducing it to a single-agent planning problem. Then, we use the solution to this single-agent problem as a skeleton plan, that each agent attempts to complete separately. We describe different variants of this idea, and in particular, suggest a method that models information about each agent’s knowledge and incorporates the idea of signaling information to other agents through actions. We perform an extensive empirical evaluation over new and old domains, demonstrating the enhanced scalability of our method.

It is essential for a collaborative robot to consider the Theory of Mind (ToM) when interacting with humans. Indeed, performing an action in the absence of another agent may create false beliefs like in the well-known Sally & Anne Task [1]. The robot should be able to detect, react to, and even anticipate false beliefs of other agents with a detrimental impact on the task to achieve. Currently, ToM is mainly used to control the task execution and resolve in a reactive way the detrimental false beliefs. Some works introduce ToM at the planning level by considering distinct beliefs, and we are in this context. This work proposes an extension of an existing human-aware task planner and effectively allows the robot to anticipate a false human belief ensuring a smooth collaboration through an implicitly coordinated plan. First, we propose to capture the observability properties of the environment in the state description using two observability types and the notion of co-presence. They allow us to maintain distinct agent beliefs by reasoning directly on what agents can observe through specifically modeled Situation Assessment processes, instead of reasoning of action effects. Then, thanks to the better estimated human beliefs, we can predict if a false belief with adverse impact will occur. If that is the case then, first, the robot’s plan can be to communicate minimally and proactively. Second, if this false belief is due to a non-observed robot action, the robot’s plan can be to postpone this action until it can be observed by the human, avoiding the creation of the false belief. We implemented our new conceptual approach, discuss its effectiveness qualitatively, and show experimental results on three novel domains.

Collaborative Multi-Agent Planning (MAP) problems with uncertainty and partial observability are often modeled as Dec-POMDPs. Yet, in deterministic domains, Qualitative Dec-POMDPs can scale up to much larger problem sizes. The best current QDec solver (QDec-FP) reduces MAP problems to multiple single-agent problems. In this paper, we describe a planner that uses richer information about agents’ knowledge to improve upon QDec-FP. With this change, the planner not only scales up to larger problems with more objects, but it can also support signaling, where agents signal information to each other by changing the state of the world.

In many real-world scenarios, the time it takes for a mobile agent, e.g., a robot, to move from one location to another may vary due to exogenous events and be difficult to predict accurately. Planning in such scenarios is challenging, especially in the context of Multi-Agent Pathfinding (MAPF), where the goal is to find paths to multiple agents and temporal coordination is necessary to avoid collisions. In this work, we consider a MAPF problem with this form of time uncertainty, where we are only given upper and lower bounds on the time it takes each agent to move. The objective is to find a safe solution, which is a solution that can be executed by all agents and is guaranteed to avoid collisions. We propose two complete and optimal algorithms for finding safe solutions based on well-known MAPF algorithms, namely, A* with Operator Decomposition (A* + OD) and Conflict-Based Search (CBS). Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. We also explore the option of online replanning in this context, i.e., modifying the agents' plans during execution, to reduce the overall execution cost. We consider two online settings: (a) when an agent can sense the current time and its current location, and (b) when the agents can also communicate seamlessly during execution. For each setting, we propose a replanning algorithm and analyze its behavior theoretically and empirically. Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost.