Assessment of BAR: Breakdown Agent Replacement Algorithm for SCRAM

2. Role Assignment Problem

Scalable Collision-avoiding Role Assignment with Minimal-makespan for Formational Positioning (SCRAM) is a role assignment and positioning system that generalizes well to many realistic and real-world MAS (MacAlpine, Price, Stone, 2015). The key criterion of SCRAM is the distance that the agents travel until reaching their target positions. SCRAM scales up to thousands of agents with effective role assignment and positioning in such a way that there is a perfect mapping of agents with a collision free and minimal makespan (minimum time for all agents to reach their target locations). Minimizing the time for the agents to reach their target positions is a key factor in functioning when agents are moving to goal positions to complete a shared operation where all agents must be in place before the task can be completed and/or started. Such tasks include those requiring agents be coordinated when they start jobs at their target positions and environments.

Role assignment problem is the problem of task allocation to the different agents in MAS so that the agents from the current position could reach to the next position in minimum time also avoiding any collision. SCRAM has been shown to satisfy the following two properties so as to perfectly assign the roles to the agents, also known as being CM valid (Collision-avoiding with Minimal-makespan):

• 1.

  Minimizing longest distance:

The longest distance from an agent to the goal, with respect to all possible mappings, is minimized. (Property 1)

• 2.

  Avoiding collisions:

The agents move to their positions without colliding with any other agent. (Property 2)