Just like humans, robots are often able to achieve more complex tasks or execute more efficient plans when working together. By leveraging robot interactions, we are able to perform more complex actions, increase throughput of multi-robot systems, and utilize varied capabilities of heterogeneous multi-robot systems. Interaction planning requires both task level planning to decide when and where to use interactions and motion planning to execute the coordination motions required of the interaction.
In order to efficiently utilize interactions, we have developed the Interaction Template Method.
Interaction Template Method
The current state-of-the-art solutions for problems with robot interactions is to emply some form of task and motion planning to reason about which robots should conduct the interaction. These methods take a 'task first' approach to planning and verify semantic actions by calling a motion planning to check geometric feasibility. When considering large multi-robot teams and potentially complex motions required for interactions, these task first approaches fail to scale effeciently. The Interaction Template Method instead offers a scalable motion planning first approach.
There are two main novelties in the Interaction Template Method. The first is the modeling of the coordinated motions of an interaction in a reusable template (interaction template). The second is the embeddeding of task semantics into a motion planning roadmap for the entire multi-robot system enabling effecient multi-robot task and motion planning.
Algorithm
An Interaction Template (IT) models a possible interaction between a pair of robots. It is composed od a pair of small roadmaps which are built up around a pair of configurations that define the relative position of an interaction. These configurations are connected with an interaction edge, which represent a possible task flow instead of a robot state change. This can be the physical passing of an object, or the symbolic passing of a role, or any other distinction that can constitue a task. In a payload transport problem, this could represent the (un)loading of a box as the 'task' would pass from the manipulator to the truck or vice versa.
These templates are generated in a vacuum and must be transformed in to locations in the environment where interactions have the potential to be useful. In the payload transport problem, they could be placed at the loading docks. A method is presented later for determining possible locations for interactions between robots with both overlapping and disjoint workspaces.
Robot-types refer to a subset of homogeneous robots in a multi-robot system. We define robot-type roadmap as a roadmap connecting all the ITs of the same robot-type.
The IT method aims to employ interactions in required and optional cooperation problems by solving a motion planning problem. This is done by generating a combined roadmap composed of all robot-type roadmaps connected via interaction edges in ITs. The combined roadmap contains roadmaps for each of the robot-types in the MRS and edges representing a way for the task flow to move between robot-type roadmaps via an interaction.
The problems can then be solved by performing a motion planning query across the combined roadmap. This provides an advantage over TMP methods that must consider the action space as the combined roadmap scales linearly with the number of robot types, however, the action space increases at a rate of |R|^2 as the number of robots increase.
The path generated across the combined roadmap represents the task flow for the MRS including necessary robot motions and interactions. Any time the path crosses between robot-type roadmaps by traversing an interaction edge, an interaction between robot-types must occur. The path can also traverse an interaction edge between configurations of the same robot-type modeling an interaction between homogeneous robots.
Related Publications
Interaction Templates for Multi-Robot Systems, James Motes, Read Sandstrom, Will Adams, Tobi Ogunyale, Shawna Thomas, Nancy M. Amato, IEEE Robotics and Automation Letters, Vol: 4, Issue: 3, pp. 2926-2933, Jun 2019. DOI: 10.1109/LRA.2019.2923386 @article{motes2019interaction, This letter describes a framework for multi-robot problems that require or utilize interactions between robots. Solutions consider interactions on a motion planning level to determine the feasibility and cost of the multi-robot team solution. Modeling these problems with current integrated task and motion planning (TMP) approaches typically requires reasoning about the possible interactions and checking many of the possible robot combinations when searching for a solution. We present a multi-robot planning method called Interaction Templates (ITs), which moves certain types of robot interactions from the task planner to the motion planner. ITs model interactions between a set of robots with a small roadmap. This roadmap is then tiled into the environment and connected to the robotsÃÂÃÂÃÂâÃÂÃÂÃÂÃÂÃÂÃÂÃÂàindividual roadmaps. The resulting combined roadmap allows interactions to be considered by the motion planner. We apply ITs to homogeneous and heterogeneous robot teams under both required and optional cooperation scenarios, which previously required a task planning method. We show improved performance over a current TMP planning approach.
Keywords: Interaction, Multi-Agent, Task Planning
Links : [Published] BibTex
title={Interaction templates for multi-robot systems},
author={Motes, James and Sandstr{\"o}m, Read and Adams, Will and Ogunyale, Tobi and Thomas, Shawna and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},
volume={4},
number={3},
pages={2926--2933},
year={2019},
publisher={IEEE}
}Abstract