MAPS-X: Explainable Multi-Robot Motion Planning via Segmentation

Multi-robot motion planning (MMP) is a fundamental challenge in robotics and artificial intelligence (AI). The goal in MMP is to plan trajectories for multiple robots according to their dynamics to reach their respective goal regions such that, when the plans are executed simultaneously, every robot (agent) successfully completes its trajectory without colliding with other agents or obstacles. Applications of MMP can be found in many areas where several moving agents interact in a shared workspace. One limitation of various AI tools, including MMP, is their inability to explain their decisions and actions to human users [1]. In many safety-critical application domains, such as air-traffic control and hazardous material warehouses, MMP tools are rarely utilized if at all. Instead, the trajectories are either hand designed or, if a planner is used, the generated paths are given to a human-supervisor for safety verification before execution. Thus, these settings require the plan to be presented in a humanly-understandable manner. Specifically, the presentation should enable the supervisor to understand the path taken by individual agents and to verify that the agents do not collide. To this end, the goal of this work is to present a method of generating explainable motion plans for multi-agent systems.

In general, MMP is NP-Complete even in the discrete (finite space) setting and naturally becomes intractable in the continuous (space) setting as the number of robots grows. A significant body of work is dedicated to overcoming this difficulty, both in the discrete domain (e.g., [2, 3]) and continuous domain (e.g., [4, 5, 6, 7]). There are two general approaches to MMP: centralized methods, which work in the composed space of all the agents [8, 6, 7], and de-centralized approaches, which divide the problem into several subproblems and solve each separately [9, 10, 11, 12]. The focus of all these works is to overcome the general difficulty of computing a plan in a short amount of time and optimizing the plan according to a measure such as makespan and path length. These works do not take into consideration the explainability of the plan. In fact, explainability often conflicts with other optimality measures and requires separate treatment.

Significant effort has been dedicated to providing explanations for problems in AI and machine learning. For example, work [13] utilizes visualization to explain the result of certain machine learning algorithms that often come up with complicated classifiers. In [14], explanations are given by analyzing alternative plans with some user-defined properties. In [15], a user proposes a plan, and explanations are given as a minimal set of differences between the actual plan and the proposed plan. A broader approach was later given in [16], where multiple types of explanations are allowed. In that setting, the user can change the plan, motivating the planner to either explain why the original plan is better or to re-plan. None of these studies, however, focus on the MMP problem.

In [17], we propose an explanation scheme based on visualization for MMP in discrete domains. There, in order to convince a human supervisor that a suggested plan does not cause a collision between the agents, the plan is decomposed into time segments, such that within each segment the paths of the agents are disjoint (i.e., non-intersecting). Then, an explanation of the plan comprises a sequence of images representing each segment. An example of such explanations for three continuous agents is shown Fig. 1. It is important to note that, since identification of line intersections is made very early in the cognitive process (namely in the primary visual cortex) [18, 19], it is easy for a human to verify that in each segment, the paths do not intersect. Moreover, the sequence of images is potentially (and indeed, often in practice) much shorter than displaying, e.g., a slowed-down video of the agents taking their paths, and is hence easy to verify. In addition, [17] showed that finding optimal explanations for a given motion plan can be done in polynomial time, whereas generating plans for explainability, i.e., limiting the number of segments, is, at best, NP-Complete.

The algorithms proposed in [17] are based on a discrete (or discretized) environment, and thus overlook the challenges involved with motion planning in the continuous domain. In this work, we focus on MMP with explanations for realistic robotic systems in the continuous space with kinodynamical constraints. To this end, we treat explainability as an additional constraint on top of MMP, and incorporate it into existing sampling-based algorithms. As mentioned above and shown in [17], there is often a trade-off between planning for short explanations and short paths. Hence, explainability may conflict with state-of-the-art heuristics for MMP. In order to factor out precise heuristics, we devise generic meta-algorithms, that search for optimally-explainable plans using any centralized sampling-based algorithm. We demonstrate our meta algorithms by plugging them with classical motion planners such as rapidly-exploring random trees (RRT) [20].

The main contribution of this work is an explanation scheme for MMP that is based on path segmentation in the continuous domain. This scheme introduces a new constraint (challenge) to the motion planning problem that is not previously studied, to the best of our knowledge. We present two meta algorithms called multi-agent plan segmenting-X (MAPS-X), where X can be any existing centralized (kinodynamic) MMP planner. Another contribution is an extensive evaluation of these algorithms, highlighting their generality and differences in performance.

Consider $k\in\mathbb{N}$ robotic systems (agents), in a shared workspace $W\subseteq\mathbb{R}^{2}$ which includes a finite set of obstacles $O$, where each obstacle $o\in O$ is a closed subset of $W$, i.e., $o\subset W$. The motion of each agent $i\in\{1,2,\ldots,k\}$ is subject to the following dynamic constraint:

Given a time interval $[t_{0},t_{f}]$, where $t_{0},t_{f}\in\mathbb{R}_{\geq 0}$ and $t_{0}<t_{f}$, a controller $\mathbf{u}_{i}:[t_{0},t_{f}]\to U_{i}$, and initial state $x_{i,0}\in X_{i}$, function $f_{i}$ can be integrated up to time $t_{1}\leq t_{f}$ to form a trajectory segment $\mathbf{x}_{i}^{t_{0}:t_{1}}$ for agent $i$, where $\mathbf{x}_{i}^{t_{0}:t_{1}}(t_{0})=x_{i,0}$. For $s\in\mathbb{N}$ consecutive time intervals,

we define a trajectory

where $\mathbf{x}_{i}^{t_{l-1}:t_{l}}(t_{l})=\mathbf{x}_{i}^{t_{l}:t_{l+1}}(t_{l})$ for all $l\in\{1,2,\ldots,s-1\},$ to be a set of $s$ trajectory segments.

Let $X_{i}^{G}\subset X_{i}$ and $x_{i,0}\in X_{i}$ denote the goal region (destination) and initial state of agent $i$, respectively. The goal multi-robot motion planning (MMP) is to find a trajectory $T_{i}$ with $\mathbf{x}_{i}(t_{0})=x_{i,0}$ for every agent $i\in\{1,2,\dots,k\}$ such that no agent collides with any obstacles nor with other agents, and $\mathbf{x}_{i}(t_{f})\in X_{i}^{G}$. In explainable MMP we require that, in addition, the interval $[t_{0},t_{f}]$ can be segmented to at most $r\in\mathbb{N}$ consecutive time intervals (for some user-defined upper bound $r$), such that within each time interval, the trajectories are disjoint when presented to the user.

To formally define the explainable MMP problem, we start by formalizing the notion of disjoint segments. Let $\textsc{proj}_{W}^{X_{i}}:\mathbb{R}^{n_{i}}\rightarrow W$ be a function that projects a state $x_{i}\in X_{i}$ of agent $i$ onto workspace $W$. Then, we call two trajectory segments $\mathbf{x}_{i}^{t_{1}:t_{2}}$ and $\mathbf{x}_{j}^{t_{1}:t_{2}}$ disjoint if

We extend the notion of disjoint from segments to trajectories as follows. Given the $s$ time intervals from (2), we call a set of trajectories $T=\{T_{1},T_{2},\ldots,T_{k}\}$ segment-disjoint if for every segment $l\in\{1,2,\ldots,s\}$ the induced trajectory-segments $\mathbf{x}_{i}^{t_{l-1}:t_{l}}\in T_{i}$ and $\mathbf{x}_{j}^{t_{l-1}:t_{l}}\in T_{j}$ are disjoint for all $i,j\in\{1,2,\ldots,k\}$ and $i\neq j$.

We can now formulate the explainable MMP problem as follows.

Note that the segment-disjoint requirement for the trajectories in Problem 1 implies that the trajectories do not cause collisions between the agents. Further, a solution to this problem consists of not only $k$ valid trajectories but also a decomposition of these trajectories into $s$ set of disjoint segments. The explanations are then $s$ images, one image per set of segments projected onto the workspace $W$, e.g., Fig. 1(b)-1(d).

We emphasize that our goal in this work is not to design an efficient algorithm that solves the general MMP problem. Rather, our goal is to design meta algorithms that turn an existing MMP planner into an explainable MMP that solves Problem 1. Specifically, we focus on centralized MMP, where planning takes place in the compound space of the agents. This approach has two advantages: first, centralized algorithms maintain most of the structure of the search space. This allows us to obtain optimal explanations (segments), which in turn sets a baseline by which to compare more involved algorithms for explainable MMP. Second, centralized planning uses well-understood algorithms, which enable us to reason about the explanations we obtain with respect to different algorithms. In contrast, de-centralized MMP algorithms may be too involved to separate their properties from the explanations they yield. We discuss incorporating explanations into more involved algorithms in Section V.

Finally, we remark that our definitions of disjoint trajectory segments is based on trajectory intersections. This definition (and the proposed algorithms) can be easily extended to intersections of robots with 2D shapes.

In this section, we present three methodologies to solve Problem 1. These are based on a centralized approach to MMP, so we first present Planner X, which is a generic centralized sampling-based tree planner. Then, we define a post-process procedure that can minimally decompose (i.e., explain) an existing MMP solution, e.g., returned by Planner X, into disjoint segments. Next, we outline two frameworks that can be incorporated into Planner X to solve explainable MMP queries.

In this section, we demonstrate the efficacy of our explanation scheme and evaluate the performance of the proposed meta-algorithms Lazy MAPS-X and MAPS-X. We implemented these algorithms with the classical motion planners RRT [20] and EST [21] and evaluated their performance in several environments and agents dynamics. The benchmarking results are shown in Table I.

Our implementations use the Open Motion Planning Library (OMPL) [22] and are available here [23]. The benchmarks were performed on a machine with AMD Ryzen 7 3.9 GHz CUP and 64 GB of RAM.

This work outlines a new aspect of MMP by considering explanation schemes for plans. The MAPS-X framework can be readily plugged on to existing (centralized) planners in order to provide explainable plans. As we showed, using MAPS-X to find short explanations sometimes generates longer plans, but can also make plans neater (at the cost of computational time). In future work, we plan to add explanation generation to state-of-the-art techniques, and in particular to decentralized approaches, in order to improve scalability.