Abstract
One of the representative problems of multi-agent systems is the graph exploration for package delivery. In this paper, we analyze the effect of the number of agents and network structure on efficiency of exploration on warehousing systems. In the package delivery, not only overcrowding but also stopping of agents for loading and unloading package cause traffic jams. This paper motivates to evaluate a relationship between stopping of agents and exploration efficiency. In this paper, we introduce the incident ID which expresses the stopping of an agent and formulate outbreak, merging, and splitting conditions of traffic jams from model of movement and stopping of agents on ASEP network, and two dimensional grid exploration. With the formulated conditions, we represent the area of traffic jams as Wait-for graph. The novelty of this paper is to evaluate the scale of the traffic jams based on the length and width of the Wait-for graphs. We also derive the expansion and reduction speeds for the derived length and width of traffic jams. The first result is to derive the cancellation conditions of the traffic jams using its expansion speed of length. The second result is to evaluate influence on exploration efficiency decrease due to the traffic jam using its expansion and reduction speed of width. For the verification of the derived cancellation conditions, expansion speeds, and reduction speeds, we show the numerical experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Azadeh K, de Koster M, Roy D (2017) Robotized warehouse systems: developments and research opportunities. Soc Sci Res Netw 2017:1–61
Bai X, Cao M, Yan W, Ge SS (2020) Efficient routing for precedence-constrained package delivery for heterogeneous vehicles. IEEE Trans Autom Sci Eng 17(1):248–260
Wu N, Zhou MC (2003) AGV routing for conflict resolution in AGV system. In: International Conference on robotics and automation, vol 1, pp 14–19
Kalinovcic L, Petrovic T, Bogdan S, Bobanac V (2011) Modified banker’s algorithm for scheduling in multi-AGV systems. In: IEEE International Conference on automation science and engineering, vol 2011, pp 351–356
Reveliotis SA (2000) Conflict resolution in AGV systems. IIE Trans 32:647–659
Derrida B, Evans MR, Hakim V, Pasquier V (1993) Exact solution of a 1D asymmetric exclusion model using a matrix formulation. J Phys A 26:1493–1517
Schadschneider A, Schreckenberg M (1993) Cellular automaton models and traffic flow. J Phys A 26:1–7
Neri I, Kern N, Parmeggiani A (2011) Totally asymmetric simple exclusion process on networks. Phys Rev Lett 107:068702
Siberschatz A, Galvin PB, Fagne G (2005) Operating system concepts. John Wiley & Sons Ltd, Hoboken
Funding
This paper is funded by JSPS KAKENHI Grant Number JP20K20314, JP19K04444, JP19H02163, and JP17H06293.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
'Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
About this article
Cite this article
Mochizuki, Y., Sawada, K. An analysis of expansion and reduction speeds of traffic jams on graph exploration. Artif Life Robotics 27, 487–494 (2022). https://doi.org/10.1007/s10015-021-00721-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10015-021-00721-y