7.7.2 Multiple-Robot Optimality

Suppose that there are two robots as shown in Figure 7.42. There is just enough room to enable the robots to translate along the corridors. Each would like to arrive at the bottom, as indicated by arrows; however, only one can pass at a time through the horizontal corridor. Suppose that at any instant each robot can either be on or off. When it is on, it moves at its maximum speed, and when it is off, it is stopped.^7.4Now suppose that each robot would like to reach its goal as quickly as possible. This means each would like to minimize the total amount of time that it is off. In this example, there appears to be only two sensible choices: 1) ${\cal A}_1$ stays on and moves straight to its goal while ${\cal A}_2$ is off just long enough to let ${\cal A}_1$ pass, and then moves to its goal. 2) The opposite situation occurs, in which ${\cal A}_2$ stays on and ${\cal A}_1$ must wait. Note that when a robot waits, there are multiple locations at which it can wait and still yield the same time to reach the goal. The only important information is how long the robot was off.

Figure 7.42: There are two Pareto-optimal coordination plans for this problem, depending on which robot has to wait.

Thus, the two interesting plans are that either ${\cal A}_2$ is off for some amount of time, $t_{off}>0$, or ${\cal A}_1$ is off for time $t_{off}$. Consider a vector of costs of the form $(L_1,L_2)$, in which each component represents the cost for each robot. The costs of the plans could be measured in terms of time wasted by waiting. This yields $(0,t_{off})$ and $(t_{off},0)$ for the cost vectors associated with the two plans (we could equivalently define cost to be the total time traveled by each robot; the time on is the same for both robots and can be subtracted from each for this simple example). The two plans are better than or equivalent to any others. Plans with this property are called Pareto optimal (or nondominated). For example, if ${\cal A}_2$ waits $1$ second too long for ${\cal A}_1$ to pass, then the resulting costs are $(0,t_{off}+1)$, which is clearly worse than $(0,t_{off})$. The resulting plan is not Pareto optimal. More details on Pareto optimality appear in Section 9.1.1.

Another way to solve the problem is to scalarize the costs by mapping them to a single value. For example, we could find plans that optimize the average wasted time. In this case, one of the two best plans would be obtained, yielding $t_{off}$ average wasted time. However, no information is retained about which robot had to make the sacrifice. Scalarizing the costs usually imposes some kind of artificial preference or prioritization among the robots. Ultimately, only one plan can be chosen, which might make it seem inappropriate to maintain multiple solutions. However, finding and presenting the alternative Pareto-optimal solutions could provide valuable information if, for example, these robots are involved in a complicated application that involves many other time-dependent processes. Presenting the Pareto-optimal solutions is equivalent to discarding all of the worse plans and showing the best alternatives. In some applications, priorities between robots may change, and if a scheduler of robots has access to the Pareto-optimal solutions, it is easy to change priorities by switching between Pareto-optimal plans without having to generate new plans each time.

Now the Pareto-optimality concept will be made more precise and general. Suppose there are $m$ robots, ${\cal A}^1$, $\ldots$, ${\cal A}^m$. Let $\gamma$ refer to a motion plan that gives the paths and timing functions for all robots. For each ${\cal A}^i$, let $L_i$ denote its cost functional, which yields a value $L_i(\gamma) \in [0,\infty]$ for a given plan, $\gamma$. An $m$-dimensional vector, $L(\gamma)$, is defined as

$$L(\gamma) = (L_1(\gamma),L_2(\gamma),\ldots,L_m(\gamma)) .$$ (7.28)

Two plans, $\gamma$ and $\gamma^\prime$, are called equivalent if $L(\gamma) = L(\gamma^\prime)$. A plan $\gamma$ is said to dominate a plan $\gamma^\prime$ if they are not equivalent and $L_i(\gamma) \leq L_i(\gamma^\prime)$ for all $i$ such that $1 \leq i \leq m$. A plan is called Pareto optimal if it is not dominated by any others. Since many Pareto-optimal plans may be equivalent, the task is to determine one representative from each equivalence class. This will be called finding the unique Pareto-optimal plans. For the example in Figure 7.42, there are two unique Pareto-optimal plans, which were already given.