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 the throughput of multi-robot systems, and utilize the 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 for interaction).

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.

Publications

Updated: