Mehdi Dadvar - Task and Motion Planning for MAS

Task and Motion Planning for Multi-Agent Systems

In dynamic environments, where the number and location of tasks are unknown to agents, robots need to explore the environment to find tasks before accomplishing them. In most real-world problems, robots need to be sufficiently dexterous, which inevitably makes robots relatively heavy and incapable of agile exploration. In this project, we aim to address this problem by considering each task composed of sequential subtasks, each possible to be done only by a certain type of agent. We Introduced the notion of hunter-and-gatherer approach to address different aspects of the problem such as multi-agent task allocation, exploration, and coordination.

First, we addressed the problem from multi-agent task allocation point of view:

Multi-Agent Task Allocation in Complementary Teams: A Hunter-and-Gatherer Approach

M. Dadvar, S. Moazami, H. R. Myler, H. Zargarzadeh

[BibTex] [PDF] Complexity 2020

abstract: Consider a dynamic task allocation problem, where tasks are unknowingly distributed over an environment. is paper considers each task comprising two sequential subtasks: detection and completion, where each subtask can only be carried out by a certain type of agent. We address this problem using a novel nature-inspired approach called “hunter and gatherer.” e proposed method employs two complementary teams of agents: one agile in detecting (hunters) and another skillful in completing (gatherers) the tasks. To minimize the collective cost of task accomplishments in a distributed manner, agame-theoreticsolution is introduced to couple agents from complementary teams. We utilize market-based negotiation models to develop incentive-based decision-making algorithms relying on innovative notions of “certainty and uncertainty profit margins.” e simulation results demonstrate that employing two complementary teams of hunters and gatherers can effectually improve the number of tasks completed by agents compared to conventional methods, while the collective cost of accomplishments is minimized. In addition, the stability and efficacy of the proposed solutions are studied using Nash equilibrium analysis and statistical analysis, respectively. It is also numerically shown that the proposed solutions function fairly; that is, for each type of agent, the overall workload is distributed equally.

Secondly, we addressed the problem from multi-agent coordination standpoint:

A Dynamic Territorializing Approach for Multi-Agent Task Allocation

M. M. Islam, M. Dadvar, H. Zargarzadeh

[BibTex] [PDF] Complexity 2020

abstract: In this paper, we propose a dynamic territorializing approach for the problem of distributing tasks among a group of robots. We consider the scenario in which a task comprises two subtasks—detection and completion; two complementary teams of agents, hunters and gatherers, are assigned for the subtasks. Hunters are assigned with the task of exploring the environment, i.e., detection, whereas gatherers are assigned with the latter subtask. To minimize the workload among the gatherers, the proposed algorithm utilizes the center of mass of the known targets to form territories among the gatherers. The concept of center of mass has been adopted because it simplifies the task of territorial optimization and allows the system to dynamically adapt to changes in the environment by adjusting the assigned partitions as more targets are discovered. In addition, we present a game-theoretic analysis to justify the agents’ reasoning mechanism to stay within their territory while completing the tasks. Moreover, simulation results are presented to analyze the performance of the proposed algorithm. First, we investigate how the performance of the proposed algorithm varies as the frequency of territorializing is varied. Then, we examine how the density of the tasks affects the performance of the algorithm. Finally, the effectiveness of the proposed algorithm is verified by comparing its performance against an alternative approach.

Finally, we addressed the problem from multi-agent exploration perspective:

Exploration and Coordination of Complementary Multirobot Teams in a Hunter-and-Gatherer Scenario

M. Dadvar, S. Moazami, H. R. Myler, H. Zargarzadeh

[BibTex] [PDF] Complexity 2021

abstract: The hunter-and-gatherer approach copes with the problem of dynamic multirobot task allocation, where tasks are unknowingly distributed over an environment. This approach employs two complementary teams of agents: one agile in exploring (hunters) and another dexterous in completing (gatherers) the tasks. Although this approach has been studied from the task planning point of view in our previous works, the multirobot exploration and coordination aspects of the problem remain uninvestigated. This paper proposes a multirobot exploration algorithm for hunters based on innovative notions of “expected information gain” to minimize the collective cost of task accomplishments in a distributed manner. Besides, we present a coordination solution between hunters and gatherers by integrating the novel notion of profit margins into the concept of expected information gain. Statistical analysis of extensive simulation results confirms the efficacy of the proposed algorithms compared in different environments with varying levels of obstacle complexities. We also demonstrate that the lack of effective coordination between hunters and gatherers significantly distorts the total effectiveness of the planning, especially in environments containing dense obstacles and confined corridors. Finally, it is statistically proven that the overall workload is distributed equally for each type of agent which ensures that the proposed solution is not biased to a particular agent and all agents behave analogously under similar characteristics.