This Chapter contributes to the understanding of intentional cooperation in multi-robot systems. It is shown that in a complex multi-robot system comprising several individual agents, each of which capable of interacting with their surroundings, cooperation is achieved implicitly through mediation of independent decisions that are made autonomously. It is claimed that in order for a multi-robot system to accomplish the objective, it is necessary for the individuals to proactively contribute to planning, to incremental refinement, as well as to adaptation at the group-level as the state of the mission progresses. It is shown how the decomposition of a mission delegated to a multi-robot system provides the system with capability of distributed decision-making. While formulating decision mechanism, it is shown how state of every agent with respect to the mission is viewed as two mutually exclusive internal and external states. Furthermore, it is demonstrated that the requirement of a priori knowledge in decision process is prevented via incorporating a simple sub-ranking mechanism into the external state component of the robotic agent. While such independent involvement preserves autonomy of the agents, it is shown that the mediation of such independent decisions does not only ensure proper execution of the plan but serves as a basis for evolution of intentional cooperation among individuals. The chapter develops and analyzes systematic approaches for mission decomposition that are formulated on a robust mathematical basis, yet exhibit high flexibility and extendibility as per mission specifications. It demonstrates a novel decision mechanism based on subdivision of internal and external states of robot with respect to a delegated mission. This prevents the requirements of a priori knowledge for decision-making through a simple opportunistic ranking module. The chapter also studies the performance of the proposed decision mechanism in contrast to the Bayesian formulism to demonstrate the results of decision process in the absence of a priori information. The chapter also introduces two novel multi-robot coordination strategies capable of preserving group level optimality of resultant allocations throughout the operation, solely based on the independent decisions of individual agents. It examines the performance of these coordination strategies in comparison to the leader-follower, the prioritization, the instantaneous, and the time-extended allocation strategies to demonstrate the optimality of its allocation strategy.
TopIntroduction
Recent advancements in cooperative robotics have elevated the field within the robotics research community. Some of the advantages that can be achieved via deployment of such systems include improved system performance, distributed action at a distance and fault tolerance. For a multi-agent system to reach the interconnectivity, interoperability and distributedness, required to preserve the autonomy of the agents to an acceptable degree, it is necessary for the agents to cooperate, reach agreement, or even compete with other systems/entities with conflicting/opposing interests. An immediate outcome of this perspective is the necessity for agents to have the capacity to make proactive, real-time decisions, individually as well as collectively and as per group-level interest and performance. Multi-robot systems are suitable for such domains when the overall task of the system is composed of several sub-goals/tasks (e.g., foraging, rescue mission) or the task is monolithic in nature, but its fulfillment requires cooperative engagement of several agents(e.g., enclosing an intruder, box-pushing, and alike).
An inherent characteristic of a cooperative multi-robot system is the necessity for a robust decision-making and allocation strategy that distributes and redistributes available tasks among agents in an efficient way, given the system as well as delegated mission specifications. Some strategies attempt to achieve optimality through deterministic modeling of system behavior, thereby bypassing the entire decision-making step. Others infer the expected behavior of the system at consecutive execution cycles through explicit reference to and direct incorporation of contributions of agents to the overall performance of the system. Since the coordination of multi-robot system is essentially the comparative analysis of selective conclusions on available alternatives, within multi-robot system research community the utility or the fitness function (a.k.a payoff function) plays an influential and prevailing role. More specifically, individual estimates on costs and rewards associated with execution of the delegated tasks provide a measure based on which conclusion on optimal performance of system is determined. Estimating costs and rewards at individual level is the first step for achieving cooperative behavior among teammates. In order to devise agents with the capability of performing delegated tasks reliably while expending least resources possible and accumulating maximum achievable rewards, the coordination of individual decisions is paramount.
For example, the market-based approaches are mostly static in finalizing decisions. In addition, all tasks are assigned via a central controller and before the commencement of the mission. Single-task assignment is yet another limitation of market-based strategies. These strategies require the entire task space to be divided into number of subtasks each of which consists of one task while the problem of assignment and coordination is solved individually and sequentially. Some market-based approaches attempt to alleviate the aforementioned shortcomings by either allowing agents to trade their tasks or by combining the central assignment of multiple tasks, followed by inter-agent trading of their corresponding assignments. However, this solution is infeasible since it duplicates the decision-making and coordination tasks by first making pre-assignments via the introduction of central coordinator and then the trading takes place among agents at the individual level. Therefore, scalability is another drawback of market-based approaches.
Although central schedulers provide the system with a supervisory ability, the susceptibility of these approaches to fault-tolerance makes them less practical. In general, assigning the authority of decision-making and coordination for the entire group to one entity, whether a central scheduler or a teammate that plays the role of leader, leaves the system with no decision to be performed in advent of communication loss with that entity. It is a suitable approach for the small-to the mid-size robotic teams. However, the overwhelming amount of information to process as number of tasks and/or robotic agents increases makes the idea less appealing. This is due to computational complexity for group-level consensus/inference.