Intelligent Algorithm for Assignment of Agents to Human Strategy in Centralized Multi-agent Coordination

摘要

Problem: Multi-agent coordination is an important issue in the domain of disaster emergency response operations where a team of agents (field units or robots) aims to achieve a joint objective. The responsibility of the Incident Commander (IC) is to (Ⅰ) specify an effective strategy composed of a number of threads (a set of prioritized sub-problems), (Ⅱ) appropriately assign/allocate agents to these threads as a strategic decision, and (Ⅲ) release agents in a timely manner from the assigned threads to adapt a strategic decision to a new situation. Objective: The purpose of this paper is to present an intelligent algorithm that assists a human in multi-agent coordination by providing two key functions: 1) automatically calculate and present a set of feasible alternatives for selecting a choice as a strategic decision in a definite time, and 2) autonomously and in a timely manner identify a subset of assigned agents that should be released from their threads in order to refine a strategic decision. Method: This algorithm expands a decision tree from a state node in which a thread (or several threads) has received a set of new agents from either the IC or a higher thread. Each thread is associated with one level of a decision tree with a number of nodes. A thread calculates a set of efficient coalitions using all the available agents and generates a new node for each coalition to show what agents are allocated to the thread and what agents are released into a lower thread. In real-time, this algorithm continuously observes and monitors the task environment to identify a subset of the assigned agents that cannot provide efficient capabilities for their threads and should be released for assignment to other threads. Results: To gather further insight, this paper applied this algorithm for team coordination to a simulated search & rescue scenario in an earthquake disaster-affected area where the team's goal was to rescue trapped people distributed in five operational zones. The result was an infinite set of alternative scenarios for a human-defined strategy. The calculated alternatives were presented to the IC for selection according to his intuition or for delegation to the system to determine an optimal strategy.