Acta Polytechnica CTU Proceedings doi:10.14311/APP.2015.1.0040 Acta Polytechnica CTU Proceedings 2:40–44, 2015 © Czech Technical University in Prague, 2015 available online at http://ojs.cvut.cz/ojs/index.php/app PLANNING AND COORDINATION IN DRIVING SIMULATION Martin Schaefer Department of Computer Science, FEE, CTU in Prague, Czech Republic correspondence: martin.schaefer@fel.cvut.cz Abstract. We present an overview of coordination and planning tasks that we face with during the development of the AgentDrive simulation platform. We particularly describe an integration of the AgentDrive with a driving simulator OpenDS. We demonstrate how the planning and coordination mechanisms can be applied in a driving simulator for automated driving applications or realistic traffic generation. We emphasize particular planning and/or coordination methods that were already developed using AgentDrive platform. Keywords: autonomous driving, driving simulation, automated driving, ADAS, automotive, multi- agent systems, agent-based simulation, multi-agent coordination. 1. Introduction Safety and efficiency of the road traffic transport sys- tems are common goals in the related research areas. Automotive industry keeps producing safer and more efficient cars to reach these goals. There is a boom of intelligent solutions to make driving safer, efficient and comfortable. There are passive safety systems followed by active ones in modern cars. Active safety systems are represented by a scale of driver assistance systems as emergency braking systems, lane-assist system, automated parking features, etc. These, so called Advanced Driver Assistance Systems (ADASs), are possibly just a step to a fully automated driving. The concept of the fully autonomous car, mostly ad- vertised by Google, is well known. The increasing automation in driving should bring the desired safety and efficiency of the road traffic. The road traffic efficiency from traffic perspective is often optimized by controlling traffic flows centrally in the road network. Differently, the safety, apart the high-level precautions, is mostly assured individually by on-board systems of each single vehicle. The dis- tribution of the responsibility over vehicles is natural with regards to the distributed physical manner of the domain. The road traffic is a multi-agent system. The distributed agents have usually several common desires, e.g, the safety. On the other hand, there is a competition for the limited resources, i.e., the road network capacity. The private properties of the in- dividual cars and also their heterogeneity motivate multi-agent paradigm to be suitable. Verification of such a complex and critical multi- agent system is difficult. Coordination mechanisms are not directly applicable in the real world traffic. The cost of the experiments with a real hardware is high. The simulation is a tool to be used to evaluate the concepts before the real world deployment. We will describe several particular coordination and planning tasks in this domain on the particular ex- ample of the integration of AgentDrive and OpenDS. Figure 1. OpenDS simulator view, highway scenario The AgentDrive platform is being developed to allow to design, prototype and evaluate agent-based coordi- nation mechanisms [1]. OpenDS is an open sourced driving simulator (see Figure 1). The AgentDrive plat- form is introduced in [1]. The driver assistance system developed on the top of the integration of AgentDrive and OpenDS is described in [2]. In this paper, we will refer to the integration of AgentDrive and OpenDS as the simulation platform. 2. Simulation platform The integration of AgentDrive with a driving simu- lator is motivated by the need to involve the human factor into the simulation of autonomous road traffic. The driving simulation brings the capability to let a human driver to be a part of the simulation, i.e., human-in-the-loop simulation. Also, the driving simu- lation works as a physics simulator for the AgentDrive simulation. On the other hand the AgentDrive brings the functionality of a traffic simulation (map data based scenarios, demand modelling, road network structures, etc.). And mainly, it allows to develop agent-based coordination mechanisms on the top of the traffic and the driving simulation. The Figure 2 shows the components of the simulation platform. In the following sections, we present the main task 40 http://dx.doi.org/10.14311/APP.2015.1.0040 http://ojs.cvut.cz/ojs/index.php/app vol. 2/2015 Planning and Coordination in Driving Simulation Driving simulation Physical Sim. HMI 3D Vis. Human Driver SUMO OSM Scenario Traffic analysis2D visualization Road Network Multi-Agent Coordination Coordination module SRTM 3D Model Driving Simulation Figure 2. Simulation platform architecture, the Driving Simulation module represents OpenDS part and the module on right is the AgentDrive platform. Note, we use OpenStreetMap data for the road traffic generation. that simulation platform is ready to perform. The tasks are overlapping in several aspects. Moreover, combinations of the tasks are also possible to be done. We present the categories for better organization and readability. 2.1. Traffic Studies The simulation is reasonable if it is able to reflect the important features of the studied real world situation. In the context of the road traffic we aim to instanti- ate the traffic so it corresponds to the real one. The defining aspects are: amount of vehicles on the road, distribution of the origin and the destination locations and the local behaviour of the vehicles/drivers. This can be achieved by a static routing and scheduling of the traffic. Having such a traffic generated, we can study, for example, the effects of different local behaviour of the vehicles/drivers on the global traffic flow. As the local behaviour can have significant ef- fect on the traffic, the original static routing and road utilization can become irrelevant. This usually leads to the usage of a mobility demand model instead of the static traffic instantiation. The mobility demand model describes the origin and the destination loca- tions of trips in time. In this case, online routing and driver models are needed to perform the simulation. 2.2. Human Factors Studies It is important to consider the human factor when a new technology is about to be deployed. Nowa- days, drivers are fully responsible for controlling the cars. All the technologies that are about to pene- trate the road traffic need to be acceptable for the human drivers. Moreover, the technologies should help drivers, not to distract them, nor to make them be less aware of the driving. The driving simulators are used to study human factors. Also, in our simulation platform the OpenDS is used to incorporate the human into the simulation 3. The OpenDS also allows the researcher to analyse the experiment in the analyser part of the simulator. The external devices to track driver’s behaviour, e.g, stress, attention, can be used. The OpenDS provides the researchers with a possibility to export the experiment outputs directly into the reports. Our main interest is particularly in the human factors in automated driving or driving with the advanced driver assistance systems. Such studies require (apart the mentioned driving simulator features) the automated driving or ADAS support respectively. We dedicate a separate section to both of these wide areas. 2.3. Driver Assistance System Studies Assistance systems are one of the ways to bring au- tomation into the traffic. Driver assistance systems should help drivers to observe the traffic situation by sensors and eventually warn the driver of the danger. Active systems, e.g., emergency braking systems, can even intervene in case of emergency. There are several aspects of ADAS to research. First, it is the develop- ment or prototyping of such a system. Later on, it is important to study the effects of such a system on the driver’s behaviour and in consequence on the safety. Also, we can refer to the studies of the effects on traffic discussed in 2.1. There is a significant effect on the traffic flow even with only few vehicles equipped with ADAS (published in [3]). 41 Martin Schaefer Acta Polytechnica CTU Proceedings Figure 3. The basic human-in-the-loop simulation setting for human factor studies The simulation platform needs to provide a re- searcher with a human-in-the-loop simulation and support for ADAS functionality support. The human- in-the simulation features are similar to the ones de- scribed in the human factors section. On the top of it, the external dashboard availability is desired for the implementation of the ADAS interface. The ADAS functionality support means that the simulation platform has to offer a way to implement the particular functionality of the system. Usually, it means to provide sensory data and an interface for the presentation of the outputs of the system to the driver. The interface can be an already mentioned output to the external dashboard or a human-machine interface (HMI) directly in the simulation visualiza- tion. In case of active ADAS, it is needed to provide a mechanism how the ADAS can intervene into the controlling of the vehicle. The logic of the assistance system is often in the scope of sensor processing, sensor fusion, reasoning and eventually the control theory. The first two phases related to sensors can be replaced by a model of a sen- sor in the simulated environment. If there are no real sensory data, it is possible to present a sensor model with a defined uncertainty instead of applying sen- sor processing on the artificial data. The mentioned reasoning stands for motion planning, trajectory pre- diction, pathfinding, etc.. The reasoning is then in the focus of our interest, it is where the coordination and planning is applicable. 2.4. Connected Car Studies Connected cars term stands for vehicles that are equipped with communication devices that allow them to communicate with other vehicles (V2V), infrastruc- ture (V2I) or with manufacturer, emergency services and others (V2X). The communication device can be approached as a sensor. Then, the communication sensor can be used for collective localization or world mapping. The communication sensor is providing the reasoning unit with an additional information that can be used for the reasoning. Connectivity is well utilized in the cooperative set- ting. Here, the communication channel is used as an infrastructure for cooperative protocols. More ad- vanced cooperative techniques can be beneficial but the high demands on the connection is often a draw- back of such approaches. 2.5. Autonomous Driving Studies Autonomous or driver-less vehicles is a wide research field. It offers also many cooperative and planning solutions to be applied. The AgentDrive platform is primary designed to support a development of the multi-agent coordination and planning algorithms. Driving simulation is not explicitly needed for au- tonomous driving as there is no driver any more. Nev- ertheless, the driving simulation is useful for many purposes in the autonomous driving related studies. It is not realistic that all the vehicles become driver-less overnight. So, there will be a period of time when there are human-driven vehicles and driver-less cars on the road at the same time. Also, the autonomous driving could be firstly applied to only controlled ar- eas or situations (e.g., highways), so the driver will need to share the responsibility with the computer. Completely different application of autonomous driving is in automated traffic generation for a driving simulation. Mostly, if the traffic is present in the driv- ing simulation, it is scripted to perform just a really basic model of a reactive traffic. Then, the algorithms to control an autonomous vehicle can be used to gen- erate a more realistic and autonomous traffic for a better driving simulation experience. 3. Planning and Coordination Applications The integration of OpenDS and AgentDrive is built on the idea to perform studies described in the previous section. It shows, that the planning and coordination applications play a key role in our simulation platform. This section presents the particular already developed applications of coordination and planning. such appli- cations form a toolbox for the previously mentioned studies. 3.1. Routing and Navigation Routing is the shortest path planning problem on the road network graph. The problem is well known and a simple Dijkstra’s or A* algorithm are applicable on the problem. The graph edges can be weighted according to the travelling speed and the occupation of the roads. This allows the vehicles to optimize the routing according the actual traffic as it is commonly done nowadays in navigation application. Also, the online rerouting is applicable if it is desired. The routing algorithm from the current location is used in this case. 42 vol. 2/2015 Planning and Coordination in Driving Simulation The navigation is a routing on the finer graph. The routing is performed on the level of lanes in this case. It is used for proper lane navigation, so that the vehicle is able to get into the desired lane changing lanes. 3.2. Driver Assistance Systems We have already developed several solutions related to the ADAS. The applications are all related to the highway driving. Highways are the simpler domain for assistance systems like an Adaptive Cruise Con- trol (ACC) or Lane Change Assists (LCA). We can consider only longitudinal dimension to be continuous, the lanes are considered to be discrete in the highway domain. In [2] we demonstrate how the AgentDrive is suitable for ADAS development. The integrated Cooperative Adaptive Cruise Control and Coopera- tive Lane Change Assist was developed and presented in [4] and [5]. We employed a Safe-Distance method originally designed in [6] to provide a driver with an assistance. The driver with the assistance was advised to change speed or to change lane by the assistance system. The results show that the drivers claimed the decreased cognitive load with the activated assistance system. Another interesting extension of the ACC is presented in [7]. The author claims that the ACC func- tionality for linear space (i.e., vehicles in line) could be extended for in junction coordination. It is possible if we are able to project the junction situation (i.e., vehicles approaching from different directions) into the linear space. 3.3. Local Coordination Algorithms The purpose of such algorithms is to control vehicles so that the vehicles follow their desired paths while avoiding collisions with each other. The algorithms can be applied to the fully controlled vehicles, i.e., autonomous driving, or to feed the Advanced Driver Assistance Systems. There are several approaches to the road traffic coor- dination. The basic approach is a reactive mechanism, where an agent representing a vehicle observes the neighbourhood and reacts to it. The Safe-Distance method presented in [6] is an example of a such ap- proach. The main idea of the method is in the main- taining a safe distance between the vehicles. An action that an agent performs must result into a safe state. A vehicle is in a safe state when the vehicle can perform a sequence of actions that leads the vehicle to stop without any collision. The method is described in detail in [6] or its gener- alization is in [8]. The generalization allows to use the method on the general road network with junctions, not only on the highway without crossings as it was constrained in the original work. The inspiration for the generalization is in the lane merging when the vehicles must merge into a single lane. The vehicles must create a gap for a vehicle in the next lane. The similar concept can be applied in the junctions, we can imagine a junction as the single lane we need to Figure 4. Visualization of junction passing using the ORCA algorithm merge into. The gaps are virtually created when ap- proaching the junction and the junction is then passed smoothly. The same core algorithm is also mentioned in Section 3.2 in the context of the generalized ACC. Another reactive coordination method is based on the Optimized Reciprocal Collision Avoid- ance (ORCA) [9]. We applied the state-of-the art algorithm for the multi-robot collision avoidance in the road traffic domain (see 4. In contrast to the previous Safe-Distance method, the ORCA is a free ride algorithm based on the velocity obstacles. The advantage of that is that it is independent of the lanes on the road, but at the same time it can be its disad- vantage. The application into the driving simulation shows that the ORCA could perform better in uti- lization of the road capacity. On the other hand it is not compatible with the current traffic as it does not respect the lanes and behaves unpredictably for the human drivers. Junctions and coordination on the junction is often a separate problem in the road traffic coordination. The setting with the traffic lights is simple, the vehicles must follow the instructions of the central authority through the traffic lights. The optimization of the timing and similar studies are in scope of pure traffic simulations. The junctions without the centralized coordination are in practice controlled by the rules defining who gives a way to who. We already presented the generalized Safe-Distance method that can serve as a coordination method in junctions in our simulations. There is no give a way sign or concept of main street, the priority comes from the position to the junction. Also, the multi-agent planning is able to maintain collision free junction passing. The asynchronous de- centralized prioritized planning (ADPP) method for road vehicles coordination was proposed and applied 43 Martin Schaefer Acta Polytechnica CTU Proceedings in [10] and in detail in [11]. The prioritized planning is a good approach to reduce computation complex- ity of the multi-agent planning, however, the priority assignment is an open problem. The static priority assignment is a simple but not convenient and com- patible solution with the current traffic rules, the dynamic priority assignment is a challenge for the future research. The cited work on ADPP for the road traffic already presented several adjustments of the algorithm so that it is applicable in the highly dy- namic traffic domain. As an example, we can mention dynamic constraints introduced to model dynamism of the road vehicles. Another cooperative technique based on the peer-to- peer algorithm was researched in [12]. The approached suffered from the excessive peer-to-peer communica- tion in case of a conflict in plans. The cooperation in sense of plan sharing was adopted also in works related to the platooning. The platooning is a concept of vehicle trains. The advan- tages of the platoons are fuel reduction, road utiliza- tion efficiency and reduction of driver load. platooning is mostly spelled in context of the commercial truck transportation. The control theory aspects with the presence of the communication was studied in [13]. The focus on formations of the vehicles and the ef- fects of the platoons on the traffic flow was described in [14]. The coordination algorithms form the core of the simulation platform. The simulation platform is de- signed to allow a wide range of in terms of compu- tation resources usage, empirical solution quality or subjective user experience. 4. Conclusions We presented the integration of AgentDrive and OpenDS. We presented the main areas that the sim- ulation platform can be used in. We emphasize the requirements of each of the areas. We identify that the integrated simulation platform contains several planning and coordination applications. The applica- tions were listed, categorized and presented to show the work done using the simulation platform. Also, we mention open issues in the related research fields. The content gives a view on the application possibilities of the simulation platform. Acknowledgements This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS15/209/OHK3/3T/13. References [1] M. Schaefer, J. Vokrinek. Agentdrive: towards an agent-based coordination of intelligent cars. In Advances in Practical Applications of Agents, Multi-Agent Systems, and Sustainability: The PAAMS Collection, pp. 211–224. Springer International Publishing, 2015. doi:10.1007/978-3-319-18944-4_18. [2] M. Schaefer, J. Vokrinek. Developing agent-based driver assistance systems using agentdrive. In Advances in Practical Applications of Agents, Multi-Agent Systems, and Sustainability: The PAAMS Collection, pp. 312–315. Springer, 2015. doi:10.1007/978-3-319-18944-4_35. [3] A. Kesting, M. Treiber, M. Schönhof, et al. Jam-avoiding adaptive cruise control (acc) and its impact on traffic dynamics. In Traffic and Granular Flow 05, pp. 633–643. Springer, 2007. doi:10.1007/978-3-540-47641-2_62. [4] J. Vokrinek, M. Schaefer, D. Pinotti. Multi-agent traffic simulation for human-in-the-loop cooperative drive systems testing. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pp. 1691–1692. International Foundation for Autonomous Agents and Multiagent Systems, 2014. [5] M. Schaefer, J. Vokrinek, D. Pinotti, F. Tango. Multi- agent traffic simulation for development and validation of autonomic car-to-car systems. In Autonomic Road Transport Support Systems. Birkhauser Basel, IN PRINT. [6] M. Schaefer. Noncooperative collision avoidance of road vehicles, 2011. [7] D. Kubeša. Autonomous cruise control for general collision avoidance of road vehicles. In Proceedings of the 19th International Scientific Student Conferenece POSTER 2015. Czech Technical University in Prague, 2015. [8] D. Kubeša. Collision avoidance on general road network, 2015. Bachelor’s Thesis. [9] M. Schaefer. Collision Avoidance of Highway Traffic. Master’s thesis, Czech Technical University in Prague, 2014. [10] M. Vavřinec, M. Schaefer. Prioritized planning for road vehicles coordination. In Proceedings of the 19th International Scientific Student Conferenece POSTER 2015. Czech Technical University in Prague, 2015. [11] M. Vavřinec. Asynchronous decentralized prioritized planning for cooperative vehicles, 2015. Bachelor’s Thesis. [12] P. Janovský. Cooperative collision avoidance of road vehicles, 2011. [13] M. Švandrlík. Convoy platooning using vehicle to vehicle communication. Master’s thesis, České vysoké učení technické v Praze. Vypočetní a informační centrum., 2015. [14] O. Borovec. Cooperative formations on highway, 2015. Bachelor’s thesis. 44 http://dx.doi.org/10.1007/978-3-319-18944-4_18 http://dx.doi.org/10.1007/978-3-319-18944-4_35 http://dx.doi.org/10.1007/978-3-540-47641-2_62 Acta Polytechnica CTU Proceedings 2:40–44, 2015 1 Introduction 2 Simulation platform 2.1 Traffic Studies 2.2 Human Factors Studies 2.3 Driver Assistance System Studies 2.4 Connected Car Studies 2.5 Autonomous Driving Studies 3 Planning and Coordination Applications 3.1 Routing and Navigation 3.2 Driver Assistance Systems 3.3 Local Coordination Algorithms 4 Conclusions Acknowledgements References