Abstract
Coverage path planning (CPP) finds the shortest feasible paths passing through all points of an environment while avoiding obstacles. Previous studies usually assume that a robot has infinite power and can fully cover the workspace with only one charge, but most mobile robots run under a limited energy budget. This study focuses on the CPP problem for a mobile robot with constrained energy power that satisfies two main optimization objectives: the total distance and the number of repeated cells. We propose a hybrid algorithm between the Boustrophedon and the partition tree group algorithms, namely B-WZone, for the CPP with energy constraints. The performance of this algorithm is compared with existing methods. The experimental results showed that the B-WZone algorithm helps the robot reduce energy consumption and traveling time in all the tested environments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Galceran, E., Carreras, M.: A survey on coverage path planning for robotics. Robot. Auton. Syst. 61(12), 1258–1276 (2013)
Bormann, R., Jordan, F., Hampp, J., Hagele, M.: Indoor coverage path planning: survey, implementation, analysis. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 1718–1725. IEEE (2018)
Sharma, G., Dutta, A., Kim, J. H.: Optimal online coverage path planning with energy constraints. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1189–1197 (2019)
Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59, 3 (1992)
Shnaps, I., Rimon, E.: Online coverage of planar environments by a battery powered autonomous mobile robot. IEEE Trans. Autom. Sci. Eng. 13(2), 425–436 (2016)
Wei, M., Isler, V.: Coverage path planning under the energy constraint. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 368–373. IEEE (2018)
Wei, M., Isler, V.I.: A log-approximation for coverage path planning with the energy constraint. In: Proceedings International Conference on Automated Planning and Scheduling, ICAPS, vol. 2018, pp. 532–539
Choset, H., Pignon, P.: Coverage path planning: the boustrophedon cellular decomposition. In: Proceedings of International Conference on Field and Service Robotics (1997)
Choset, H., Acar, E., Rizzi, A.A., Luntz, J.: Exact cellular decompositions in terms of critical points of Morse functions. In: Proceedings IEEE International Conference Robotics and Automation ICRA2000, vol. 3, pp. 2270–2277 (2018)
Strimel, G.P., Veloso, M.M.: Coverage planning with finite resources. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2014, pp. 2950–2956. IEEE (2014)
Mishra, S., Rodriguez, S., Morales, M., Amato, N.M.: Battery-constrained coverage. In: IEEE International Conference on Automation Science and Engineering (CASE), pp. 695–700. IEEE (2016)
Shen, Z., Wilson, J.P., Gupta, S.: \(\epsilon ^{\star }+ \): an Online coverage path planning algorithm for energy-constrained autonomous vehicles. In: Global Oceans 2020: Singapore-US Gulf Coast, pp. 1–6. IEEE (2020)
Acknowledgment
This research is funded by Hanoi University of Science and Technology (HUST) under project number T2022-PC-042.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Giang, T.T.C., Binh, H.T.T. (2022). Hybrid Boustrophedon and Partition Tree Group Algorithm for Coverage Path Planning Problem with Energy Constraints. In: Szczerbicki, E., Wojtkiewicz, K., Nguyen, S.V., Pietranik, M., Krótkiewicz, M. (eds) Recent Challenges in Intelligent Information and Database Systems. ACIIDS 2022. Communications in Computer and Information Science, vol 1716. Springer, Singapore. https://doi.org/10.1007/978-981-19-8234-7_49
Download citation
DOI: https://doi.org/10.1007/978-981-19-8234-7_49
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-8233-0
Online ISBN: 978-981-19-8234-7
eBook Packages: Computer ScienceComputer Science (R0)