Multi-Robot Task Allocation with Inter-Agent Distance Constraints
Description
This thesis considers the problem of multi-robot task allocation with inter-agent distance constraints, e.g., due to the presence of physical tethers or communication requirements, that must be satisfied at all times. Specifically, three optimization-based formulations are explored: (i) a “Naive Method” that leverages the classical multiple traveling salesman (mTSP) formulation to find solutions that are then filtered out when the inter-agent distance constraints are violated, (ii) a “Timed Method” thatconstructs a new formulation that explicitly accounts for robot timings, including the inter-agent distance constraints, and (iii) an “Improved Naive Method” that reformulates the Naive Method with a novel graph-traversal algorithm to produce tours that,
unlike the Naive Method, allow backtracking and also introduces a more systematic approach to filter out solutions that violate inter-agent distance constraints. The effectiveness of the approaches to return task allocations that satisfy the constraints
are demonstrated and compared in simulation experiments.
Date Created
The date the item was original created (prior to any relationship with the ASU Digital Repositories.)
2023
Agent
- Author (aut): Goodwin, Walter Alexander
- Thesis advisor (ths): Yong, Sze Zheng
- Thesis advisor (ths): Grewal, Anoop
- Committee member: Xu, Zhe
- Publisher (pbl): Arizona State University