The article proposes a new path planning method for a multi-robot system for transportation with various loading conditions. For a given system, one needs to distribute given pickup and delivery jobs to the robots and find a path for each robot while minimizing the sum of travel costs. The system has multiple robots with different payloads. Each job has a different required minimum payload, and as a result, job distribution in this situation must take into account the difference in payload capacities of robots. By reflecting job handling restrictions and job accomplishment costs in travel costs, the problem is formulated as a multiple heterogeneous asymmetric Hamiltonian path problem and a primal-dual based heuristic is developed to solve the problem. The heuristic produces a feasible solution in relatively short amount of time and verified by the implementation results.
Bibliographical noteFunding Information:
The author(s) disclosed receipt of following financial support for the research, authorship, and/or publication of this article: This research was supported by the NRF, MSIP (Grant No. NRF-2017R1A2A1 A17069329) and by the Agriculture, Food and Rural Affairs Research Center Support Program (Grant No. 714002-07), MAFRA, Korea.
This research was supported by the NRF, MSIP (Grant No. NRF-2017R1A2A1 A17069329) and by the Agriculture, Food and Rural Affairs Research Center Support Program (Grant No. 714002-07), MAFRA, Korea.
© The Author(s) 2019.
- Multi-robot path planning
- functional heterogeneity
- pickup and delivery job assignment
- transportation robot system
ASJC Scopus subject areas
- Computer Science Applications
- Artificial Intelligence