A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars

• Autorzy: Burzyński Wojciech , Kaleta Mariusz

Identyfikatory

DOI

10.2478/fcds-2025-0012

• Języki publikacji: EN

Abstrakty

EN

In this paper, we introduce a novel variant of the Vehicle Routing Problem (VRP), the Rechargeable Rover Routing Problem (RRRP), which addresses the routing of energy-constrained autonomous electric rovers for Martian missions. We formulate a graphbased representation of the problem and propose an initial formulation as a mixed-integer non-linear program (MINLP). To enhance computational efficiency, we demonstrate how the model can be linearized. The resulting mixed integer linear model is evaluated on small-scale test cases, and its computational complexity is analyzed for larger problems with up to 30 Points of Interest (PoIs). Our experiments show that the problem can be solved to optimality for problem sizes anticipated in upcoming Mars expeditions. However, for future missions involving swarms of rovers, the development of more efficient heuristic or approximation algorithms will be necessary.

Słowa kluczowe

EN

task scheduling; electric VRP; VRP with profits; rover routing problem; mars exploration; MILP

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2025
• Tom: Vol. 50, No. 3
• Strony: 325--346
• Opis fizyczny: Bibliogr. 30 poz., rys., tab.

Twórcy

autor

Burzyński Wojciech

• Warsaw University of Technology, Doctoral School, Warsaw, Poland

• https://orcid.org/0009-0003-8668-7754

autor

Kaleta Mariusz

• Warsaw University of Technology, Faculty of Electronics and Information Technology, Warsaw, Poland

• https://orcid.org/0000-0002-2225-895

Bibliografia

• [1] Blazewicz J. and Kobler D. Review of properties of different precedence graphs for scheduling problems. European Journal of Operational Research, 142(3):435–443, 2002.
• [2] Burzyński W. and Kaleta M. Task scheduling for autonomous vehicles in the martian environment. In Mańdziuk J., ˙Zychowski A., and Małkiński M., editors, Progress in Polish Artificial Intelligence Research 5. Proceedings of the 5th Polish Conference on Artificial Intelligence (PP-RAI’2024) 18-20.04.2024, PP-RAI’2024, page 366-373, Warsaw, Poland, 2024. Politechnika Warszawska.
• [3] Carsten J., Rankin A., Ferguson D., and Stentz A. Global path planning on board the mars exploration rovers. In 2007 IEEE Aerospace Conference, pages 1-11, 2007.
• [4] Chien S., Barrett A., Estlin T., and Rabideau G. A comparison of coordinated planning methods for cooperating rovers. In Proceedings of the Fourth International Conference on Autonomous Agents, AGENTS ’00, page 100-101, New York, NY, USA, 2000. Association for Computing Machinery.
• [5] Colby M., Yliniemi L., and Tumer K. Autonomous multiagent space exploration with high-level human feedback. Journal of Aerospace Information Systems, 13(8): 301-315, 2016.
• [6] Dobson A., Solovey K., Shome R., Halperin D., and Bekris K. Scalable asymptotically-optimal multi-robot motion planning. Autonomous Robots, 44, 03 2020.
• [7] Elshaer R. and Awad H. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering, 140: 106242, 2020.
• [8] Ghrist R., O’Kane J. M., and LaValle S. M. Pareto Optimal Coordination on Roadmaps, pages 171-186. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.
• [9] Gunawan A., Kendall G., McCollum B., Seow H.-V., and and L. S. L. Vehicle routing: Review of benchmark datasets. Journal of the Operational Research Society, 72(8): 1794-1807, 2021.
• [10] Huang Y., Wu S., Mu Z., Long X., Chu S., and Zhao G. A multi-agent reinforcement learning method for swarm robots in space collaborative exploration. In 2020 6th International Conference on Control, Automation and Robotics (ICCAR), pages 139-144, 2020.
• [11] Huntsberger T., Pirjanian P., Trebi-Ollennu A., Das Nayar H., Aghazarian H., Ganino A., Garrett M., Joshi S., and Schenker P. Campout: a control architecture for tightly coupled coordination of multirobot systems for planetary surface exploration. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 33(5): 550–559, 2003.
• [12] Karaman S. and Frazzoli E. Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30: 846-894, 2011.
• [13] Konstantakopoulos G. D., Gayialis S., and Kechagias E. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational research, 22(3): 2033-2062, 2022.
• [14] Kucukoglu I., Dewil R., and Cattrysse D. The electric vehicle routing problem and its variations: A literature review. Computers & Industrial Engineering, 161: 107650, 2021.
• [15] Le D. and Plaku E. Guiding sampling-based tree search for motion planning with dynamics via probabilistic roadmap abstractions. IEEE International Conference on Intelligent Robots and Systems, pages 212-217, 10 2014.
• [16] Le D. and Plaku E. Cooperative, dynamics-based and abstraction-guided multi-robot motion planning. J. Artif. Int. Res., 63(1): 361-390, sep 2018.
• [17] Lee C. An exact algorithm for the electric-vehicle routing problem with nonlinear charging time. Journal of the Operational Research Society, 72(7): 1461-1485, 2021.
• [18] Martins L. d. C., Tordecilla R. D., Castaneda J., Juan A. A., and Faulin J. Electric vehicle routing, arc routing, and team orienteering problems in sustainable transportation. Energies, 14(16), 2021.
• [19] NASA. High resolution imaging experiment (hirise) website. https://mars.nasa.gov/mro/mission/instruments/hirise/. Acesssed: (2024-02-11).
• [20] Nayak S., Paton M., and Otte M. W. A heuristic-guided dynamical multi-rover motion planning framework for planetary surface missions. IEEE Robotics and Automation Letters, 8(5): 2542-2549, 2023.
• [21] Nayak S., Yeotikar S., Carrillo E., Rudnick-Cohen E., Jaffar M. K. M., Patel R., Azarm S., Herrmann J. W., Xu H., and Otte M. Experimental comparison of decentralized task allocation algorithms under imperfect communication. IEEE Robotics and Automation Letters, 5(2): 572-579, 2020.
• [22] Petrovsky A., Kalinov I., Karpyshev P., Tsetserukou D., Ivanov A., and Golkar A. The two-wheeled robotic swarm concept for mars exploration. Acta Astronautica, 194: 1-8, 2022.
• [23] Sherwood R., Mishkin A. H., Chien S. A., Estlin T. A., Backes P. G., Cooper B. K., Rabideau G. R., and Engelhardt B. An integrated planning and scheduling prototype for automated mars rover command generation. 2001.
• [24] Tahami H., Rabadi G., and Haouari M. Exact approaches for routing capacitated electric vehicles. Transportation Research Part E: Logistics and Transportation Review, 144: 102126, 2020.
• [25] Tompkins P., Stentz A., and Wettergreen D. Global path planning for mars rover exploration. In 2004 IEEE Aerospace Conference Proceedings (IEEE Cat. No.04TH8720), volume 2, pages 801-815 Vol.2, 2004.
• [26] van den Berg J. and Overmars M. Prioritized motion planning for multiple robots. In 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 430-435, 2005.
• [27] Švestka P. and Overmars M. H. Coordinated path planning for multiple robots. Robotics and Autonomous Systems, 23(3): 125-152, 1998.
• [28] Wagner G., Kang M., and Choset H. Probabilistic path planning for multiple robots with subdimensional expansion. In 2012 IEEE International Conference on Robotics and Automation, pages 2886-2892, 2012.
• [29] Yang Z., Zhao Q., Lv X., Wang L., and Liu W. Multiple robots autonomous task planning based on improved genetic algorithm. In 2024 IEEE International Conference on Robotics and Biomimetics (ROBIO), pages 547-552, 2024.
• [30] Çağrı Koç, Bektas¸ T., Jabali O., and Laporte G. A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows. Computers & Operations Research, 64: 11-27, 2015.