Robot-Robot Systems

While most previous research on forming coalitions concentrates mainly on loosely coupled multirobot tasks, a more challenging problem is to address tightly coupled multirobot tasks that involve close robot coordination, which often requires capability sharing. General methods for autonomous capability sharing have been shown to greatly improve the flexibility of distributed systems. However, in addition to the interaction constraints between the robots and the environment required by the tasks, these methods may introduce additional interaction constraints between robots based on how the capabilities are shared. The satisfiability of these constraints in the current situation determines the feasibility of potential coalitions.

To achieve system autonomy, the ability to identify potential coalitions that are feasible for task execution is critical. We introduce a general approach that incorporates this capability, extending the ASyMTRe architecture into IQ-ASyMTRe, which is able to find coalitions in which these required constraints are satisfied. When used to form coalitions, IQ-ASyMTRe sets up only feasible coalitions, enabling tasks to be executed autonomously. We have formally proven that IQ-ASyMTRe is sound and complete for forming executable coalitions.

In IQ-ASyMTRe, robot capabilities are built as schemas based on schema theory, where each schema represents a motor, sensory, computational, or communication capability of the agent. Given a task, we must determine how to connect the different schemas of different robots to satisfy the task’s requirements.

To create the solution space of potential connection solutions for a task, the reasoning algorithm first checks all components that can output the required information instances for the task, then checks recursively for the inputs of those components until each path either ends in a source component (such as a sensor) or in a conflict with the referent instantiation constraint, which requires the referents of certain information instances to be instantiated to the same entity in the environment. In a second phase, the robots temporarily activate their capabilities to dynamically instantiate the information flows from sources to sinks.

A robot assigned to a task may need to form a coalition due to capability and physical constraints, and for a multirobot task, multiple coalitions may need to be formed. Although approaches exist to form coalitions, no general architecture previously existed to execute these coalitions when they can overlap.

In FLOW, we identify three main challenges to achieving such an architecture for tightly coupled multirobot tasks: creating and validating coordination solutions with potentially overlapping coalitions; executing the task while maintaining the coalitions subject to environmental influences; and relaxing the coalitions and coordination solution when they become infeasible. The proposed architecture is built on the concept of information flow, which defines the interactions among basic functional units, or schemas, on robots. FLOW addresses the first challenge by formalizing coalitions as information flows that specify configuration constraints to be satisfied in the coordination solution; the second is converted to monitoring and maintaining a measure of flow quality, computed systematically from the flow structure; and the third is associated with flow relaxation, which allows information to flow in alternative ways.

In FLOW, we propose a coordination mechanism to address coalition execution. It provides a flexible method to reason about synergies with overlapping coalitions, thus enabling multitasking robots in multi-robot tasks, which not only improves efficiency but also reduces resource requirements during task execution. This means that FLOW enables tasks that could not be easily handled before, especially when critical resources are rare but commonly required.

This coordination mechanism is based on the concept of sensor constraint, introduced by information sharing between robots. We have proven that this mechanism is sound and complete in finding a coordination solution given a few assumptions.

As coalitions are formed in FLOW, sensor constraints among robots are also established. How to keep these constraints satisfied throughout execution, from initial configuration to task completion, remains an open issue, and environmental factors, both static and dynamic, can influence whether the constraints continue to hold. Problems also arise when the constraints become unsatisfiable given current circumstances.

FLOW proposes a general method to address these issues across applications with different sensors. The method combines sensor models, environment sampling, and a measure of information quality with a sampled motion model. Local information-quality measures are then combined systematically to compute an overall flow quality.

In FLOW, when an information flow is interrupted, or when flow quality no longer satisfies the task’s requirements, the task robot can initiate a flow relaxation process for the affected coalition. Since this process can update the set of sensor constraints, the coordination solution also needs to be recreated. This only needs to be performed on the initiating coalition and any coalitions set up after it in the previous coordination process, unless a new coordination solution cannot be found with these coalitions after relaxation.

FLOW further improves on this by reasoning about the solution space, providing a more robust and flexible flow relaxation process.