Planning cooperative motions of multiple vehicles is a task of high computational complexity. However, real-time performance is required in applications such as cooperative collision avoidance for road vehicles, enforcing a trade-off between computing time and solution quality. In this report, several motion planning algorithms are compared with respect to these criteria. The considered algorithms are a tree search algorithm relying on precomputed lower bounds, the elastic band method, mixed-integer linear programming, and a priority-based approach. Different multi-vehicle motion planning algorithms have been evaluated on cooperative collision avoidance tasks. The state-of-the-art prioritized planner cannot solve certain problem instances due to its inherent restriction of the action space. The algorithms which exploit the composite action space of the vehicles have been more successful on these instances. In the intersection scenario, the tree search method performed best, while elastic bands and MILP showed good results in the overtaking scenarios. These observations indicate that either the algorithm should be chosen depending on the traffic scenario, or multiple planners should be executed in parallel to guarantee optimal results. Tree search and elastic bands clearly have the potential for real-time application. While the MILP method can also solve a lot of problem instances rather fast, its timing behavior appears to be too unpredictable for real-time use. Another criterion is the possibility to plan collision mitigation maneuvers. The tree search method can handle collision mitigation if the loss functional is modified so that the severity of collisions is minimized. It seems to be difficult to integrate collision mitigation in the elastic band or MILP framework, as these methods do not support arbitrary explicit models.
A comparison of algorithms for planning cooperative motions of cognitive automobiles
Joint workshop of Fraunhofer IOSB and Institute for Anthropomatics, Vision and Fusion Laboratory, 2 ; 75-90
2010
16 Seiten, 4 Bilder, 2 Tabellen, 32 Quellen
Aufsatz (Konferenz)
Englisch
Planning cooperative motions of cognitive automobiles using tree search algorithms
Fraunhofer Publica | 2010
|British Library Conference Proceedings | 2011
|Cooperative Cognitive Automobiles
IEEE | 2007
|Cooperative Cognitive Automobiles
British Library Conference Proceedings | 2007
|Fraunhofer Publica | 2011
|