Abstract
In this paper we propose a method for optimizing the design of a roadmap, used for motion coordination of groups of automated guided vehicles for industrial environments. Considering the desired flows among different locations in the environment, we model the problem as a multi-commodity concurrent flow problem, which allows us to assign the directions of the paths in an optimized manner. The proposed solution is validated by means of simulations, exploiting realistic layouts, and comparing the performance of the system with those achieved with a baseline roadmap.
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
Notes
- 1.
It is worth noting that, given a generic roadmap, multiple paths exist that connect each pair of nodes.
- 2.
It is worth noting that the most commonly traveled paths by the vehicles are generally the shortest paths. Alternative paths are chosen only in the presence of heavy traffic conditions or other unexpected events that would generate large waiting times. As an example, the reader is referred to [10].
- 3.
Differences in the maximum number of AGVs used in the simulations are due to the different size of the scenarios.
References
Abdullah, N., Hua, T.K.: Using ford-fulkerson algorithm and max flow-min cut theorem to minimize traffic congestion in Kota Kinabalu, Sabah. J. Inf. 2(4), 18–34 (2017)
Babonneau, F.: Solving the multicommodity flow problem with the analytic center cutting plane method. Ph.D. thesis, University of Geneva (2006)
Bauguion, P.O., Ben-Ameur, W., Gourdin, E.: Efficient algorithms for the maximum concurrent flow problem. Networks 65(1), 56–67 (2015)
Beinschob, P., Meyer, M., Reinke, C., Digani, V., Secchi, C., Sabattini, L.: Semi-automated map creation for fast deployment of AGV fleets in modern logistics. Robot. Auton. Syst. 87, 281–295 (2017)
Bullo, F., Cortés, J., Martínez, S.: Distributed Control of Robotic Networks. Applied Mathematics Series. Princeton University Press (2009). http://coordinationbook.info
Chien, T.Q., Lau, N.D.: Algorithm finding maximum concurrent multicommodity linear flow with limited cost in extended traffic network with single regulating coefficient on two-side lines. Int. J. Comput. Netw. Commun. (IJCNC) 9(2) (2017)
Chopin, N., Schafer, C.: Adaptive Monte Carlo on multivariate binary sampling spaces. Working Papers, Centre de Recherche en Economie et Statistique (2010)
Devaurs, D., Siméon, T., Cortés, J.: Optimal path planning in complex cost spaces with sampling-based algorithms. IEEE Trans. Autom. Sci. Eng. 13(2), 415–424 (2015)
Digani, V., Sabattini, L., Secchi, C., Fantuzzi, C.: An automatic approach for the generation of the roadmap for multi-AGV systems in an industrial environment. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Chicago, IL, USA, September 2014
Digani, V., Sabattini, L., Secchi, C., Fantuzzi, C.: Ensemble coordination approach in multi-AGV systems applied to industrial warehouses. IEEE Trans. Autom. Sci. Eng. 12(3), 922–934 (2015)
Even, S., Itai, A., Shamir, A.: On the complexity of time table and multi-commodity flow problems. In: 16th Annual Symposium on Foundations of Computer Science (SFCS 1975), pp. 184–193. IEEE (1975)
Garg, N., Koenemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630–652 (2007)
Geraerts, R., Overmars, M.H.: A comparative study of probabilistic roadmap planners. In: Boissonnat, J.-D., Burdick, J., Goldberg, K., Hutchinson, S. (eds.) Algorithmic Foundations of Robotics V. STAR, vol. 7, pp. 43–57. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-45058-0_4
Kaanodiya, K., Rizwanullah, M.: Minimize traffic congestion: an application of maximum flow in dynamic networks. J. Appl. Math. Stat. Inf. (JAMSI) 8(1), 63–74 (2012)
Moore, E.J., Kichainukon, W., Phalavonk, U.: Maximum flow in road networks with speed-dependent capacities-application to bangkok traffic. Songklanakarin J. Sci. Technol. 35(4) (2013)
Sabattini, L., et al.: The pan-robots project: advanced automated guided vehicle systems for industrial logistics. IEEE Robot. Autom. Mag. 25(1), 55–64 (2018). https://doi.org/10.1109/MRA.2017.2700325
Sabattini, L., Digani, V., Secchi, C., Fantuzzi, C.: Hierarchical coordination strategy for multi-AGV systems based on dynamic geodesic environment partitioning. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, Korea, October 2016
Sabattini, L., Secchi, C., Chopra, N.: Decentralized estimation and control for preserving the strong connectivity of directed graphs. IEEE Trans. Cybern. 45(10), 2273–2286 (2015)
Sabattini, L., et al.: Technological roadmap to boost the introduction of AGVs in industrial applications, pp. 203–208 (2013)
Tsardoulias, E., Iliakopoulou, A., Kargakos, A., Petrou, L.: A review of global path planning methods for occupancy grid maps regardless of obstacle density. J. Intell. Robot. Syst. 84(1–4), 829–858 (2016)
Vis, I.F.: Survey of research in the design and control of automated guided vehicle systems. Eur. J. Oper. Res. 170(3), 677–709 (2006)
Yamuna, M., Raza, A., Anand, K., Kumar, S., Kumar, S.: Traffic control system using maximum flow algorithm. Int. J. Curr. Eng. Technol. 6(5) (2016)
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 Switzerland AG
About this paper
Cite this paper
Digani, V., Sabattini, L. (2022). Optimized Direction Assignment in Roadmaps for Multi-AGV Systems Based on Transportation Flows. In: Matsuno, F., Azuma, Si., Yamamoto, M. (eds) Distributed Autonomous Robotic Systems. DARS 2021. Springer Proceedings in Advanced Robotics, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-92790-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-92790-5_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92789-9
Online ISBN: 978-3-030-92790-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)