University of North Florida. School of Computing
Hedonic Coalition Formation for Task Allocation with Heterogeneous Robots
Abstract
dc:description.abstractTasks in the real world are complex in nature and often require multiple robots to collaborate in order to be accomplished. However, multiple robots with the same set of sensors working together might not be the optimal solution. In many cases a task might require different sensory inputs and outputs. However, allocating a large variety of sensors on each robot is not a cost-effective solution. As such, robots with different attributes must be considered. In this thesis we study the coalition formation problem for task allocation with multiple heterogeneous (equipped with a different set of sensors) robots. The proposed solution is implemented utilizing a Hedonic Coalition Formation strategy, rooted in game theory, coupled with bipartite graph matching. Our proposed algorithm aims to minimize the total cost of the formed coalitions and to maximize the matching between the required and the allocated types of robots to the tasks. Simulation results show that it produces near-optimal solutions (up to 94%) in a negligible amount of time (0:19 ms. with 100 robots and 10 tasks).
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Computer and Information Sciences (MS)
- Discipline thesis:degree_discipline
- Computing
- Grantor
- University of North Florida. School of Computing
- Date dc:date.issued
- Fall
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Czarnecki, Emily
- Czarnecki, Emily, 1987-
- Advisors dc:contributor.advisor
-
- Dutta, Ayan
- Asaithambi, Asai
- Liu, Xudong
- Contributors dc:contributor
-
- Dr. Ayan Dutta
- Dr. Asai Asaithambi
- Dr. Xudong Liu
Subjects
dc:subject × 7- Thesis; University of North Florida; UNF; Dissertations
- Academic -- UNF -- Master of Science in Computer and Information Sciences; Dissertations
- Academic -- UNF -- Computing; coalition formation; multi-robot system; task allocation; hedonic coalition
- Artificial Intelligence and Robotics
- Computer Sciences
- Theory and Algorithms
- Heterogeneous computing -- Testing; Blocking sets -- Mathematical models -- Testing; Bipartite graphs -- Mathematical models -- Testing; Heterogeneous distributed computing systems -- Testing; Parallel processing (Electronic computers) -- Testing; Parallel robots -- Testing
Rights
dc:rightsIdentifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.unf.edu/etd/914