Loosening the Reins: Autonomous, Decentralized, Allocation of Resources and Tasks for Heterogeneous Multi-Agent Systems
(Room Innovation Hub-- Booth 2727)
03 May 16
10:00 AM
-
5:30 PM
Tracks:
Air, Ground, Maritime, Research and Development
Task assignment and allocation, a critical element in multi-agent teams, overwhelmingly remains the domain of human operators. Due to this, heterogeneous teams of autonomous vehicles require a highly trained operator within communication range of all vehicles, limiting the area of operation to radio range of the base station, introducing additional latency due to human reaction time, and creating a single point of failure. In addition, the heuristic methods used by human operators provide suboptimal solutions for small numbers of tasks, and become intractable as the system size increases. A task’s characteristics such as type, location, required time window, prerequisites and prioritization must be accounted for in order to properly distribute tasks among team members. For an agent, the agent’s speed, available paths, task competency, and resource consumption must be considered. The presentation will describe a method for removing the human in the loop and allowing fully autonomous allocation. The system’s performance, benefits, and drawbacks will be discussed, and example solutions will be shown and compared to both “greedy” and human-generated paths. The method described consists of two interconnected aspects used to generate an overall team plan: 1. Localized Planning 2. Task Negotiation Localized planning consists of how to solve the problem of a single vehicle optimizing its efforts within a large number of tasks. This problem is viewed as an extension of the well-studied “traveling salesman problem,” which states: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once, then returns to the origin city?” The following modifications, however, must be made to the standard problem in order to reflect a real world task allocation scenario: 1. The agent need not return to its origin location. 2. Each node receives a score when it is visited, consisting of a weighted combination of multiple contributions, including task priority, task completion time, task competence, and resource drain, all of which are in the range 0-1. Instead of minimizing the distance between nodes (or “cities”), as in the traveling salesman problem, the goal of this algorithm is to maximize the total path score. 3. In order to ensure that a more capable vehicle does not claim easier tasks at the cost of overall system performance, a decay function is included in the total path score. This decay function devalues the score of a task which many vehicles are capable of performing, but increases the score of a task as the path length increases so simpler tasks are not ignored by highly capable agents. 4. Each node will activate or deactivate based on the time, or on other tasks which have been completed. Agents must be capable of taking task availability into account when planning paths, and waiting for or omitting tasks which are not available. These extensions were applied to the canonical “ant colony system” solution to the traveling salesman problem demonstrated by M. Dorigo and L.M. Gambardella in 1997, maximizing score in place of minimizing distance. This method was chosen due to its favorable attitude towards complex and temporal cost functions. The negotiation aspect is an event-driven decision tree, which runs independently on each vehicle and enables cooperative behavior. It responds to information received from external sources, and serves to determine if the local path needs to be re-planned, whether or not the task should be performed by the local vehicle, and whether an update needs to be shared with other vehicles. This handles the following high level events: 1. A task is added to the system 2. A task is removed from the system 3. A new agent enters the team 4. An agent exits the team 5. An agent updates its score or removes a task from its plan due to emerging information Through the application of this decision tree and the extensions regarding localized planning, autonomous agents are able to perform decentralized task estimation and allocation among themselves without the need for human intervention. This additional capability, by removing much of the burden of control from human operators, represents a substantial leap forward in the ability to deploy multi-agent teams to solve complex systems.