{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T16:55:53Z","timestamp":1782320153916,"version":"3.54.5"},"reference-count":56,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T00:00:00Z","timestamp":1738368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>This paper addresses the challenge of coordinating task allocation and generating collision-free trajectories for a fleet of mobile robots in dynamic environments. Our approach introduces an integrated framework comprising a centralized task allocation system and a distributed trajectory planner. The centralized task allocation system, employing a heuristic approach, aims to minimize the maximum spatial cost among the slowest robots. Tasks and trajectories are continuously refined using a distributed version of CHOMP (Covariant Hamiltonian Optimization for Motion Planning), tailored for multiple-wheeled mobile robots where the spatial costs are derived from a high-level global path planner. By employing this combined methodology, we are able to achieve near-optimal solutions and collision-free trajectories with computational performance for up to 50 robots within seconds.<\/jats:p>","DOI":"10.3390\/robotics14020017","type":"journal-article","created":{"date-parts":[[2025,2,3]],"date-time":"2025-02-03T05:36:32Z","timestamp":1738560992000},"page":"17","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Simultaneous Path Planning and Task Allocation in Dynamic Environments"],"prefix":"10.3390","volume":"14","author":[{"given":"Jennifer","family":"David","sequence":"first","affiliation":[{"name":"Center for Applied Intelligent Systems Research, School of ITE, Halmstad University, SE-30118 Halmstad, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Valencia","sequence":"additional","affiliation":[{"name":"Center for Applied Intelligent Systems Research, School of ITE, Halmstad University, SE-30118 Halmstad, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,1]]},"reference":[{"key":"ref_1","unstructured":"Daniel, C., Frans, O., Hendrik, B., and Karl, T. (2017, January 8\u201312). Decentralised online planning for multi-robot warehouse commissioning. Proceedings of the 16th Conference on Autonomous Agents489 and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent490 Systems, Sao Paulo, Brazil."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Baxter, J.L., Burke, E.K., Garibaldi, J.M., and Norman, M. (2007). Multi-robot search and rescue: A potential field based approach. Autonomous Robots and Agents, Springer.","DOI":"10.1007\/978-3-540-73424-6_2"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1109\/TRO.2004.839232","article-title":"Coordinated multi-robot exploration","volume":"21","author":"Burgard","year":"2005","journal-title":"IEEE Trans. Robot."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1109\/JPROC.2006.876927","article-title":"Distributed multirobot exploration and mapping","volume":"94","author":"Fox","year":"2006","journal-title":"Proc. IEEE"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"108453","DOI":"10.1016\/j.compag.2023.108453","article-title":"Path planning for mobile robots in unstructured orchard environments: An improved kinematically constrained bi-directional RRT approach","volume":"215","author":"Ye","year":"2023","journal-title":"Comput. Electron. Agric."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"108774","DOI":"10.1016\/j.compag.2024.108774","article-title":"Dynamic visual servo control methods for continuous operation of a fruit harvesting robot working throughout an orchard","volume":"219","author":"Chen","year":"2024","journal-title":"Comput. Electron. Agric."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511546877"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1109\/70.736775","article-title":"Optimal motion planning for multiple robots having independent goals","volume":"14","author":"LaValle","year":"1998","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Van Den Berg, J.P., and Overmars, M.H. (2005, January 2\u20136). Prioritized motion planning for multiple robots. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada.","DOI":"10.1109\/IROS.2005.1545306"},{"key":"ref_10","unstructured":"Van Den Berg, J., Guy, S.J., Lin, M., and Manocha, D. (2005, January 2\u20136). Reciprocal n-Body Collision Avoidance. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s10514-014-9412-1","article-title":"Goal assignment and trajectory planning for large teams of interchangeable robots","volume":"37","author":"Turpin","year":"2014","journal-title":"Auton. Robot."},{"key":"ref_12","unstructured":"Matthew, T., Nathan, M., and Vijay, K. (2015). An approximation algorithm for time optimal multi-robot routing. Algorithmic Foundations of Robotics XI, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s10514-013-9351-2","article-title":"An anytime assignment algorithm: From local task swapping to global optimality","volume":"35","author":"Liu","year":"2013","journal-title":"Auton. Robot."},{"key":"ref_14","unstructured":"David, J., and Philippsen, R. (2016). Task Assignment and Trajectory Planning in Dynamic environments for Multiple Vehicles. Robotics Science and System, Workshop on Task and Motion Planning, IOS Press."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1008855018923","article-title":"Cooperative mobile robotics: Antecedents and directions","volume":"4","author":"Cao","year":"1997","journal-title":"Auton. Robot."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1177\/0278364904045564","article-title":"A formal analysis and taxonomy of task allocation in multi-robot systems","volume":"23","author":"Gerkey","year":"2004","journal-title":"Int. J. Robot. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1177\/0278364913496484","article-title":"A comprehensive taxonomy for multi-robot task allocation","volume":"32","author":"Ayorkor","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"ref_19","first-page":"725","article-title":"Efficient multi-robot coordination through auction-based task allocation and behavior-based execution","volume":"35","author":"Sameh","year":"2009","journal-title":"J. Artif. Intell. Res."},{"key":"ref_20","unstructured":"LaValle, S.M. (2000). Rapidly-exploring random trees: Progress and prospects. Algorithmic and Computational Robotics: New Directions: The Fourth Workshop on the Algorithmic Foundations of Robotics, CRC."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1016639210559","article-title":"Coverage for robotics\u2014A survey of recent results","volume":"31","author":"Choset","year":"2001","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_22","unstructured":"Yang, L., Gu, D., Chen, L., and Hu, H. (2018, January 12\u201315). Multi-robot task allocation for robot soccer. Proceedings of the IEEE International Conference on Robotics and Biomimetics, Kuala Lumpur, Malaysia."},{"key":"ref_23","unstructured":"Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., and Kumar, T.K. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. arXiv."},{"key":"ref_24","unstructured":"Silver, D. (2005, January 1\u20132). Cooperative pathfinding. Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, Marina Del Rey, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","article-title":"Conflict-based search for optimal multi-agent pathfinding","volume":"219","author":"Sharon","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/3564696","article-title":"Multiple Mobile Robot Task and Motion Planning: A Survey","volume":"55","author":"Antonyshyn","year":"2023","journal-title":"ACM Comput. Surv."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10846-012-9740-3","article-title":"An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments","volume":"70","author":"Moon","year":"2013","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Masehian, E., and Nejad, A.H. (2010, January 3\u20137). A hierarchical decoupled approach for multi robot motion planning on trees. Proceedings of the IEEE International Conference on Robotics and Automation, Anchorage, AK, USA.","DOI":"10.1109\/ROBOT.2010.5509572"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"5816","DOI":"10.1109\/LRA.2021.3074883","article-title":"Integrated task assignment and path planning for capacitated multi-agent pickup and delivery","volume":"6","author":"Chen","year":"2021","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Brown, K., Peltzer, O., Sehr, M.A., Schwager, M., and Kochenderfer, M.J. (August, January 31). Optimal sequential task assignment and path finding for multi-agent robotic assembly planning. Proceedings of the 2020 IEEE546 International Conference on Robotics and Automation (ICRA), Virtual.","DOI":"10.1109\/ICRA40945.2020.9197527"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Xu, X., Yin, Q., Fu, Y., and Yu, M. (2024, January 28\u201331). Solving multi-goal task assignment and path finding problem with a Single Constraint Tree. Proceedings of the 43rd Chinese Control Conference (CCC), Kunming, China.","DOI":"10.23919\/CCC63176.2024.10661528"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"103883","DOI":"10.1016\/j.tre.2024.103883","article-title":"Integrated task assignment and path planning for multi-type robots in an intelligent warehouse system","volume":"194","author":"Qiu","year":"2025","journal-title":"Transp. Res. Part Logist. Transp. Rev."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Liu, S., Feng, B., Bi, Y., and Yu, D. (2024). An Integrated Approach to Precedence-Constrained Multi-Agent Task Assignment and Path Finding for Mobile Robots in Smart Manufacturing. Appl. Sci., 14.","DOI":"10.3390\/app14073094"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Xia, G., Sun, X., and Xia, X. (2021). Multiple task assignment and path planning of a multiple unmanned surface vehicles system based on improved self-organizing mapping and improved genetic algorithm. J. Mar. Sci. Eng., 9.","DOI":"10.3390\/jmse9060556"},{"key":"ref_35","first-page":"101930","article-title":"A coordinated scheduling approach for task assignment and multi-agent path planning","volume":"36","author":"Fang","year":"2024","journal-title":"J. King Saud-Univ.-Comput. Inf. Sci."},{"key":"ref_36","unstructured":"Murphey, R.A. (2005). Integrated Assignment and Path Planning. [Doctoral Thesis, University of Florida]."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Umay, I., Fidan, B., and Melek, W. (2019, January 17\u201318). An integrated task and motion planning technique for multi-robot-systems. Proceedings of the 2019 IEEE International Symposium on Robotic and Sensors Environments (ROSE), Ottawa, ON, Canada.","DOI":"10.1109\/ROSE.2019.8790413"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"111474","DOI":"10.1016\/j.knosys.2024.111474","article-title":"An effective collaboration evolutionary algorithm for multi-robot task allocation and scheduling in a smart farm","volume":"289","author":"Guo","year":"2024","journal-title":"Knowl.-Based Syst."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/j.cor.2010.06.001","article-title":"Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms","volume":"38","author":"Edison","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.adhoc.2012.06.006","article-title":"An autonomous wireless sensor network deployment system using mobile robots for human existence detection in case of disasters","volume":"13","author":"Tuna","year":"2014","journal-title":"Ad. Hoc. Netw."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Nigam, N. (2013, January 19\u201322). Dynamic replanning for multi-UAV persistent surveillance. Proceedings of the AIAA Guidance, Navigation, and Control (GNC) Conference, Boston, MA, USA.","DOI":"10.2514\/6.2013-4887"},{"key":"ref_42","unstructured":"Emam, Y., Mayya, S., Notomista, G., Bohannon, A., and Egerstedt, M. (August, January 31). Adaptive task allocation for heterogeneous multi-robot teams with evolving and unknown robot capabilities. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Paris, France."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Luo, X., and Liu, C. (2024). Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications. arXiv.","DOI":"10.1109\/LRA.2024.3412589"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Xu, X., and de Soto, B.G. (June, January 29). Deep reinforcement learning-based task assignment and path planning for multi-agent construction robots. Proceedings of the 2nd Future of Construction Workshop at the International Conference on Robotics and Automation (ICRA 2023), London, UK.","DOI":"10.22260\/ICRA2023\/0008"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Vu, C.-T., and Liu, Y.-C. (2024, January 2\u20134). Deep Reinforcement Learning for Multi-Robot Local Path Planning in Dynamic Environments. Proceedings of the 13th International Workshop on Robot Motion and Control590 (RoMoCo), Poznan, Poland.","DOI":"10.1109\/RoMoCo60539.2024.10604387"},{"key":"ref_46","unstructured":"Zheng, Y., Li, B., An, D., and Li, N. (2015, January 15\u201317). A multi-agent path planning algorithm based on hierarchical reinforcement learning and artificial potential field. Proceedings of the 11th International Conference on Natural Computation (ICNC), Zhangjiajie, China."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Bae, H., Kim, G., Kim, J., Qian, D., and Lee, S. (2019). Multi-robot path planning method using reinforcement learning. Appl. Sci., 9.","DOI":"10.3390\/app9153057"},{"key":"ref_48","first-page":"446","article-title":"Smooth and efficient obstacle avoidance for a tour guide robot","volume":"1","author":"Philippsen","year":"2003","journal-title":"IEEE Int. Conf. Robot. Autom."},{"key":"ref_49","first-page":"321","article-title":"Deterministic Annealing based on Potts-spin model for Multi Robot Routing Problem","volume":"15","author":"David","year":"2021","journal-title":"Springer J. Intell. Robot. Syst."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"David, J., Valencia, R., Philippsen, R., and Iagnemma, K. (2018). Local Path Optimizer for an Autonomous Truck in a Harbor Scenario. Springer Field and Service Robotics: Results of the 11th International Conference, Springer.","DOI":"10.1007\/978-3-319-67361-5_32"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"David, J., Valencia, R., Philippsen, R., Bosshard, P., and Iagnemma, K. (2017, January 24\u201328). Gradient based path optimization method for autonomous driving. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada.","DOI":"10.1109\/IROS.2017.8206318"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1177\/0278364913488805","article-title":"CHOMP: Covariant Hamiltonian optimization for motion planning","volume":"32","author":"Zucker","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"970","DOI":"10.1109\/72.857776","article-title":"Local routing algorithms based on Potts neural networks","volume":"11","author":"Hakkinen","year":"2000","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"David, J., and R\u00f6gnvaldsson, T. (2021). Multi-Robot Routing Problem with Min\u2013Max Objective. Robotics, 10.","DOI":"10.3390\/robotics10040122"},{"key":"ref_55","unstructured":"Philippsen, R. (2025, January 15). Robotics Motion Planning Library. Available online: https:\/\/github.com\/poftwaresatent\/trychomp."},{"key":"ref_56","unstructured":"Pascal, B., and Roland, P. (2015). Investigation of Trajectory Optimization for Multiple Car-Like Vehicles. [Semester Thesis, Halmstad University]."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/14\/2\/17\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:25:32Z","timestamp":1760027132000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/14\/2\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,1]]},"references-count":56,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["robotics14020017"],"URL":"https:\/\/doi.org\/10.3390\/robotics14020017","relation":{},"ISSN":["2218-6581"],"issn-type":[{"value":"2218-6581","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,1]]}}}