PARTITIONING KNOWN ENVIRONMENTS FOR MULTI-ROBOT TASK ALLOCATION USING GENETIC ALGORITHMS

Authors

  • Md Maksudur R. Mazumder
  • Chris Phillips

DOI:

https://doi.org/10.47839/ijc.19.3.1897

Keywords:

task-allocation, terrain partitioning, known environments, multi-robot, exploration, Unmanned Aerial Vehicle (UAV), Genetic Algorithm (GA), search optimization

Abstract

A common challenge facing emergency services, particularly in response to fires and/or earthquakes, is the location and subsequent extraction of people from hazardous buildings in a timely manner. This usually requires emergency service workers to enter the building and put their own lives at risk, even when there may be no people to extract. However, given recent advances in autonomous robotics, drones are expected to help humans in tasks such as search and rescue, and similar tasks, where coverage and time are key parameters. The aim is to complete a comprehensive search of the environment as quickly as feasible. Using multiple drones rather than a single drone can reduce search time, although performance can be poor if the searching is non-coordinated. Therefore, partitioning a terrain is important in order to effectively distribute the drone search work so that good coverage can be achieved in a reasonable amount of time and redundant searching is eliminated. In this paper a novel Square Based Terrain Partitioning (SBTP) algorithm is presented using a genetic algorithm to partition a known environment into multiple domains in a multi-robot exploration system. In addition, a second genetic algorithm is presented to allocate the domain search workload such that, given a certain number of drones, the overall search time is minimized.

References

S. Li, X. Xu, and L. Zuo, “Task assignment of multi-robot systems based on improved genetic algorithm,” Proceedings of the IEEE International Conference on Mechatronics and Automation, Beijing, China, August 2-5, 2015, pp. 1430-1435.

T. Nagarajan, and A. Thondiyath, “Heuristic based task allocation algorithm for multiple robots using agents,” Proceedings of the International Conference on Design and Manufacturing, IConDM, 2013, pp. 844-853.

M.-H. Kim, S.-P. Kim, and S. Lee, “Social-welfare based task allocation for multi-robot systems with resource constraints,” Journal Computer and Industrial Engineering, vol. 63, no. 4, pp. 994-1002, 2012.

D. Zhang, G. Xie, J. Yu, and L. Wang, “Adaptive task assignment for multiple mobile robots via swarm intelligence approach,” Journal Robotics and Autonomous Systems, vol. 55, no. 7, pp. 572-588, 2007.

X. Chen, T. Tang, and L. Li, “Study on the real-time task assignment of multi-UCAV in uncertain environment based on genetic algorithm,” Proceedings of the IEEE 5th International Conference on Robotics, Automation and Mechatronics (RAM), 2011, pp. 73-76.

I. Younas, F. Kamrani, C. Schulte, and R. Ayani, “Optimization of task assignment to collaborating agents,” Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling (SCIS), 11-15 April, 2011, pp. 17-24.

W. Sun, W. Hu, A. Lin, H. Tang, and W. Wu, “Multi-robot task assignment in obstacle environment,” Proceedings of the 36th Chinese Control Conference, Dalian, China, July 26-28, 2017, pp. 6608-6613.

R. Calvo, A.A. Constantino, and M. Figueiredo, “Individual distinguishing pheromone in a multi-robot system for a balanced partitioned surveillance task,” Proceedings of the International Joint Conference on Neural Networks (IJCNN), 24-29 July, 2016, pp. 4346-4353.

X. Bai, W. Yan, M. Cao, and J. Huang, “Task assignment for robots with limited communication,” Proceedings of the 36th Chinese Control Conference, Dalian, China, July 26-28, 2017, pp. 6934-6939.

T.S. Dahl, M. Mataric, and G.S. Sukhatme, “Multi-robot task allocation through vacancy chain scheduling,” Robotics and Autonomous Systems, vol. 57, pp. 674-687, 2009.

X. Bai, W. Yan, and M. Cao, “Clustering-based algorithms for multivehicle task assignment in a time-invariant drift field,” IEEE Robotics and Automation Letters, vol. 4, no. 4, pp. 2166-2173, October 2017.

S. Jeon, M. Jang, D. Lee, Y.-J. Cho, and J. Lee, “Multiple robots task allocation for cleaning a large public space,” Proceedings of the SAI Intelligent Conference, London, UK, November 10-11, 2015, pp. 315-319.

N. Nedjah, R.M. de Mendonca, and L. de Macedo Mourelle, “PSO-based distributed algorithm for dynamic task allocation in a robotic swarm,” Journal International Conference on Computational Science (ICCS), vol. 51, pp. 326-335, 2015.

W. Ling, G.M. Angel, P. Domenec, S. Albert, “Voronoi-based space partitioning for coordinated multi-robot exploration,” Journal of Physical Agents, vol. 1, no. 1, pp. 37-44, 2007.

U. Jain, R. Tiwari, S. Majumder, S. Sharma, “Multi robot area exploration using circle partitioning method,” Proceedings of the International Symposium on Robotics and Intelligent Sensors (IRIS’2012), 2012, vol. 41, pp. 383-387.

Y. Elor and A.M. Bruckstain, “Multi-agent graph patrolling and partitioning,” Proceedings of the 2009 IEEE/WIC/ACM Int. Joint Conf. on Web Intelligence and Intelligent Agent Technologies, 2009, pp. 52-57.

C. Kato and T. Sugawara, “Decentralized area partitioning for a cooperative cleaning task,” Proceedings of the 16th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2013, Dunedin, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8291, pp. 470-477, 2013.

K. Yoneda, C. Kato, and T. Sugawara, “Autonomous learning of target decision strategies without communications for continuous coordinated cleaning tasks,” Proceedings of the IEEE/WIC/ACM Int. Conf. of Web Intelligence and Intelligent Agent Technologies, 2013, pp. 216-223.

Md.M.R. Mazumder, and C. Phillips, “Exploration of known environments with a multi-robot system using a genetic algorithm with a novel terrain partitioning algorithm,” Proceedings of the 9th IEEE International Conference on Intelligent Systems (IS), Funchal-Madeira, Portugal, September 25-27, 2018, pp. 371-378.

K. Deb, “Genetic algorithm in search and optimization: the technique and applications,” Proceedings of the International Workshop on Soft Computing and Intelligent Systems, 1997, pp. 58-87.

http://www.obitko.com/tutorials/genetic-algorithms/index.php (last accessed on April 14, 2018).

Downloads

Published

2020-09-27

How to Cite

Mazumder, M. M. R., & Phillips, C. (2020). PARTITIONING KNOWN ENVIRONMENTS FOR MULTI-ROBOT TASK ALLOCATION USING GENETIC ALGORITHMS. International Journal of Computing, 19(3), 480-490. https://doi.org/10.47839/ijc.19.3.1897

Issue

2020, Volume 19, Issue 3

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.