An Algorithm for Task Allocation and Planning for a Heterogeneous Multi-Robot System to Minimize the Last Task Completion Time
Open Access
Abstract
This paper proposes an algorithm that provides operational strategies for multiple heterogeneous mobile robot systems utilized in many real-world applications, such as deliveries, surveillance, search and rescue, monitoring, and transportation. Specifically, the authors focus on developing an algorithm that solves a min–max multiple depot heterogeneous asymmetric traveling salesperson problem (MDHATSP). The algorithm is designed based on a primal–dual technique to operate given multiple heterogeneous robots located at distinctive depots by finding a tour for each robot such that all the given targets are visited by at least one robot while minimizing the last task completion time. Building on existing work, the newly developed algorithm can solve more generalized problems, including asymmetric cost problems with a min–max objective. Though producing optimal solutions requires high computational loads, the authors aim to find reasonable sub-optimal solutions within a short computation time. The algorithm was repeatedly tested in a simulation with varying problem sizes to verify its effectiveness. The computational results show that the algorithm can produce reliable solutions to apply in real-time operations within a reasonable time.Keywords
This publication has 24 references indexed in Scilit:
- The influence of drone monitoring on crop health and harvest size2017
- A heuristic for a heterogeneous automated guided vehicle routing problemInternational Journal of Precision Engineering and Manufacturing, 2017
- A survey on technologies for automatic forest fire monitoring, detection, and fighting using unmanned aerial vehicles and remote sensing techniquesCanadian Journal of Forest Research, 2015
- Long‐term Mapping Techniques for Ship Hull Inspection and Surveillance using an Autonomous Underwater VehicleJournal of Field Robotics, 2015
- An ant colony optimization technique for solving min–max Multi-Depot Vehicle Routing ProblemSwarm and Evolutionary Computation, 2013
- A survey of unmanned aerial vehicles (UAVs) for traffic monitoring2013
- A Centralized Multi-Robot Task Allocation for Industrial Plant Inspection by Using A* and Genetic Algorithms2012
- Towards cooperation of heterogeneous, autonomous robots: A case study of humanoid and wheeled robotsRobotics and Autonomous Systems, 2010
- Reducibility Among Combinatorial Problems2009
- On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and TangentsAmerican Journal of Mathematics, 1957