Planar max flow maps and determination of lanes with clearance
- PDF / 7,693,244 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 1 Downloads / 189 Views
Planar max flow maps and determination of lanes with clearance Renato Farias1
· Marcelo Kallmann1
Received: 4 December 2018 / Accepted: 9 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract One main challenge in multi-agent navigation is to generate trajectories minimizing bottlenecks in environments cluttered with obstacles. In this paper we approach this problem globally by taking into account the maximum flow capacity of a given polygonal environment. Given the difficulty in solving the continuous maximum flow of a planar environment, we present in this paper a GPU-based methodology which leads to practical methods for computing maximum flow maps in arbitrary two-dimensional polygonal domains. Once a flow map representation is obtained, lanes can be extracted and optimized in length while keeping constant the flow capacity achieved by the system of trajectories. This work extends our previous work on max flow maps by presenting a clearance-based flow generation method which takes into account the size of the agents at the flow generation phase. In this way we ensure that the maximum possible number of lanes with the needed clearance is always obtained, a property that was found to not be always obtained with our previous method. As a result we are able to generate trajectories of maximum flow from source to sink edges across a generic set of polygonal obstacles, enabling the deployment of large numbers of agents utilizing the maximum flow capacity of a continuous description of the environment and eliminating bottlenecks. Keywords Path planning · Multi-agent navigation · Maximum flow · Graphics processors
1 Introduction The problem of optimally deploying multiple agents traversing a polygonal environment has important applications in many areas, as for example, to control multiple robots in warehouses, to coordinate autonomous cars across narrow streets and to evaluate evacuation scenarios. While optimality can be defined by taking into account different parameters such as energy, time, or distance traveled, in all cases the problem is difficult to be solved in a planar domain and is usually addressed in a discrete representation of the environment. This is one of the several papers published in Autonomous Robots comprising the Special Issue on Robotics: Science and Systems. Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10514-020-09917-w) contains supplementary material, which is available to authorized users.
B
Renato Farias [email protected] Marcelo Kallmann [email protected]
1
In this paper we present a method for agent deployment among obstacles based on computing the continuous maximum flow of a 2D environment. In this case we address computing solutions based on disjoint lanes which are optimal with respect to the maximum flow of agents traversing the environment. Our overall approach is based on GPU rasterization techniques which allow us to compute maximum flows from polygonal representations and to repr
Data Loading...
