IROS2019国际学术会议论文集1110

Abstract There are many different driver assistance systems that help the driver controlling their vehicle. These systems do not have full control of the car; however, there are more and more systems in development that take over individual driving functions completely. We are working towards a fully autonomous future. The goal is not only to transport people to their desired destination, but to make commuting on roads safer. Navigation is one of the essential tasks of autonomous driving. The software must independently calculate a route from its current location to the destination. If the vehicle is not guided precisely through the road network, it can never reach that destination. To cope with the problem, the data of the road network must be available to the vehicle. Based on this data, the vehicle must be able to calculate a route to its destination. This paper deals with the development of a navigation algorithm, for optimal path planning, within the framework of an industrial project. The various requirements for the realization of a navigation system are listed. Solution strategies of such systems are identified and compared. Based on this, approaches for solving the task are developed and implemented. I. INTRODUCTION The development of intelligent machines and robots are subject to some requirements and challenges. Since an autonomous vehicle is effectively nothing more than an autonomous mobile robot, many of the rules and principles of robotics can be applied. The three central questions of robotics are: Where am I? Where should I go? How do I get there? To answer them, a robot must interpret heterogeneous sensor measurements and, based on this, select and execute complex actions 1. The environmental and path-planning constraints have also to be taken into account. For vehicles these can be, e.g., fuel use or real-time accident information. Other vehicles on the road place high technical demands on autonomous driving. The system has to deal with many different road participants. These include: cars, motorcycles, trucks, mopeds, scooters, bicycles and pedestrians. In critical situations, everyone reacts differently. These situations need to be covered by the system, as autonomous and non- autonomous vehicles are involved in road traffic during the transition from classic to autonomous driving. However, technical capability is not the only problem hindering the introduction of autonomous vehicles. In addition to the safety of road users, ethics, law and acceptance are also topics that are currently being discussed by various parties 2. *Research supported by Bertrandt Ingenieurbro GmbH Cologne. M. Dinges is with Bertrandt Ingenieurbro GmbH, 50769 Cologne, Germany (phone: 015786120692; e-mail: marco.dinges). Prof. D. Schilberg is with Hochschule Bochum, 44801 Bochum, Germany (e-mail: daniel.schilberghs-bochum.de). S. Ciethier is with Bertrandt Ingenieurbro GmbH, 50769 Cologne, Germany (e-mail: stephan.ciethier). A. Hardware Overview of the Model Car Figure 1. Block diagram of the system architecture (prototype) 3 Fig. 1 shows the prototype of the model car at the beginning of the project. The motion sensor is an inertial measurement unit, which consists of several acceleration sensors and a rotation rate sensor. As a result, movements of the vehicle can be perceived. The ultrasonic sensors monitor the closer environment of the car. The front camera is used for lane detection. Lane marking information is used to determine the distance between the sidelines and the center of the vehicle. An implemented transverse control keeps the vehicle in the middle of the road. There is also a longitudinal control, which is responsible for the speed of the vehicle. A rear camera is planned, but not installed. The evaluation of the sensor and camera data, along with calculations and control commands of the vehicle, are actuated on two single- board computers, which perform different tasks. Two Raspberry Pi Model 3B are used for this 4, 5. Components not included in the prototype, but currently under development are an energy management system including a charging structure, a lidar sensor, additional ultrasonic sensors, and an ultra-wideband (UWB) positioning system. B. The Aim of this Project The main objective of this project is the development of a navigation module. Using this module, the vehicle has to be able to autonomously navigate through a road network without external interference of any kind. For the realization, the entire software module must be defined and developed independently. A street system designed in advance should be used as a basis for the implementation. The map of the road network has to be converted into a digital form and stored on a single-board computer. The core of the software module for this work is a navigation algorithm. Various search algorithms used by navigation devices are to be selected, tested and evaluated. Finally, an integration test is to be carried out in order to check the functionality of the navigation module in conjunction with the other software modules of the project. Development of a Navigation Algorithm for Optimal Path Planning for Autonomous Electric Vehicles* Marco Dinges, Daniel Schilberg, Stephan Ciethier 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) Macau, China, November 4-8, 2019 978-1-7281-4003-2/19/$31.00 2019 IEEE3740 For the realization of the software module, a Raspberry Pi Model 3B is available. The operating system is the Robot Operating System (ROS). The implementation of the navigation module and the creation of the route are subject to some specifications and requirements, which are explained in more detail in this paper. II. METHODS FOR ROUTE DETERMINATION IN ROAD NETWORKS Many different universities and institutes deal with the navigation of vehicles. For example, the dissertation by Professor Dominik Schultes 6 deals with route planning in road networks. He explains that a simple algorithm is already enough to calculate optimal routes for vehicles. The problem with this approach is that as the amount of data increases, the algorithm also takes much longer to find an optimal route. With increasingly complex road networks, the time factor becomes a very big problem. The objective is to find techniques and algorithms that accelerate this process. In order to ensure this, the data usually has to be elaborately prepared, which has a negative effect on the duration of the preprocessing. In return, an optimal route will be found much faster. A. Graphs and Search Algorithms Graphs are a model for describing structural relationships 7. They are often used to depict relationships between different objects. Examples include hierarchical structures and networks such as telephone or electricity networks 8, 9, 10. Road networks are preferably represented using graph theory. Nodes are the road intersections and edges are the connecting roads. Even special cases such as one-way streets can be represented in the form of bows 11. Usually the goal is the fastest or shortest route from start to destination. An algorithm tries to find a path from the starting node to the goal node that meets the desired requirements 1. There are multiple search algorithms, which differ in several points that are explained in the following section. 1) Overview of the Algorithms There are different properties that distinguish search algorithms from each other. If an algorithm is complete, it is guaranteed that an existing solution will be found. If it also has optimality, an optimal solution is always found. Two further characteristics are time and memory complexity. A basic distinction is made between uninformed and informed searches. Uninformed search algorithms use intuitive methods to search through a graph. Weightings of the edges are not considered. Typical examples are the breadth-first search (BFS) and the depth-first search 1. Informed search algorithms often use a heuristic to provide information in advance that improves the search 12. In this case the heuristic estimates the distance from the current location to the target goal 13. There are also informed search algorithms that do not use heuristics, like Dijkstras algorithm 1. Another well-known search algorithm, which also uses a heuristic, is the A* algorithm 14, 15. Both are used to find an optimal path. Depending on the type of heuristic and whether a closed list is used, the A* algorithm has different properties 16. In addition to completeness and optimality, the algorithm can also be optimally efficient 1. 2) Special Forms of the A* Algorithm The limiting factor when using the A* algorithm is usually the available memory space. By using a closed list, all visited nodes are saved. As a result, the amount of data increases drastically in searches that visit many nodes. There are several variations of the A* algorithm that improve the memory problem. One of them is the Iterative Deepening A*, which already intervenes in the cost calculation 16. Another variant is the recursive best search that also stores the costs of the best alternative path 16. The problem with these two algorithms is that they use less memory than may be available. While they reduce memory complexity, they can increase time complexity 16. There are algorithms that make full use of the available memory space. Two examples are the Memory Bounded A* and the Simplified Memory Bounded A* 16. These algorithms eliminate nodes from the memory once it is full. So that the optimal path is not accidentally eliminated, the costs of the deleted node are saved in a higher-level node. Here, too, the calculation time can be increased if deleted subtrees have to be reconstructed repeatedly 16. The interaction between memory and time complexity is a problem for which there is currently no solution 16. The only possibility is to leave out the optimality of the algorithm in order to make it faster or less memory intensive. Examples are the weighted A*, the dynamically weighted A* and the D* algorithm 1. These algorithms are mostly used when there are changes to the graph during runtime, because the A* algorithm cannot handle such changes 16. 3) Heuristics For route planning in navigation systems, in most cases a form of the A* algorithm is used 15. A common heuristic that is utilized is the Euclidean metric 1. However, there are several other heuristics. The Manhattan metric is often used as a heuristic for grid-like networks 17. As soon as diagonal movements are possible, a different heuristic is used to calculate the diagonal distance to the target 18. Whenever movements in all directions are possible, the Euclidean metric is used. The advantage of this heuristic is that it never overestimates the costs between the start and goal nodes and can provide lower values than the other heuristics 19. A heuristic that always finds the shortest path in the fastest time is the exact heuristic. The advantage is that the A* algorithm always examines the best possible node next and the optimal path is found. To achieve this, the best routes between all available nodes must be calculated in advance. The costs of each of these routes are then stored, which has a considerable effect on the memory consumption of the graph 18. Therefore, one should carefully consider whether it makes sense to calculate and use an exact heuristic. III. CONCEPTION OF THE NAVIGATION FOR THE MODEL CAR A. Requirements Analysis An area of 10 m * 10 m is available for the map. Since the model car turn diameter is 165 cm at the maximum steering angle, the curves on the test track must have at least such a diameter. Different values for the lane and the road markings are taken from a previous thesis. The track width is 24 cm. The markings are fixed at a width of 1.3 cm, a length 3741 of 20 cm and a gap of 40 cm between the markings 3. There are also requirements for the contents of the track. Main roads must have two lanes and there must be intersections and a roundabout. In addition, space should be provided for a parking lot and an electric vehicle charging station. Since the speed of the car is regulated in three stages 20, there will be different speed zones. The vehicle must navigate from its current location to a destination which is entered by the user. This means that the system must be able to accept coordinates as the destination input. The vehicle position and its orientation are provided by another software module. B. Design of the Track A sketch of the map is created with Inkscape 21. As shown in Fig. 2, the draft contains all specifications of the test track. The area at the top right of the figure is initially reserved for parking spaces and the charging station. At the bottom, an expressway has been added on which a speed limit of 1.2 m/s is applied. For the rest of the route the speed limit is 0.6 m/s. The tightest curves have a radius of 85 cm. It is important to note that there is not enough space to make a U-turn on the road. This criterion must be considered during implementation. Figure 2. Sketched design of the test track The designed track is converted into a graph. The routes between the individual nodes are calculated using search procedures. They are then converted into instructions that the vehicle can follow. The communication between the individual modules is realized with the help of ROS topics and services. A software architecture is created to define the relations among the different software modules. IV. IMPLEMENTATION OF THE NAVIGATION MODULE A. Basis for Development The ROS version Kinetic Kame was selected to implement the software 22. The implementation itself is written in Python 2.7. The basic idea of the digital graph, the implemented search procedures and the functions used by these come from Amits A* Pages 23. The graph and the selected algorithms are adapted to the existing framework conditions and are extended by additional required functions. In order to calculate a route, the current position of the model car is required. This data is sent by the motion software module. The interface between the motion and the navigation module is an object that comprises three 32-bit float variables. Those contain the current x-position, y- position and orientation of the vehicle. The navigation module calculates the optimal path to the destination. Afterwards it sends a request to the corresponding service and the driver module responds. This allows the driver module to confirm whether the command has been executed or not. The navigation ends as soon as the vehicle has turned into the target road. The reason for this is that no parking spaces have currently been created nor has another abort criterion been defined. B. The Navigation Graph as a Class A separate class is implemented for the graph, which forms the core of the software. It contains various attributes and methods that are needed to calculate a route. The greatest benefit in this case is that graphs of different road networks can be created as objects of this class and the attributes and methods are inherited. This means that the functions and algorithms contained in the class can be applied to any graph if it has been implemented in the given structure. 1) Generation of the Graph A node is created at each point on the map where multiple roads merge or a road divides into several roads. Additional nodes are created for the parking lot and the charging station. Edges are then created between all the nodes where there is also a connection on the map in the form of a road. A directed graph must be used so that one-way streets can also be considered. The edges must also be allocated costs. These represent a kind of effort to reach from one node to another. The graph is placed over the map in Fig. 3. Figure 3. Map including the nodes of the graph In the current graph, no information is given about what the car needs to do to reach the next node from the current node. To cope with this, the framework of connections between individual nodes is extended manually by the needed driver commands. Since there is not enough space on the roads to make a U-turn with the vehicle, it cannot always 3742 reach another node even if the nodes are connected by a road. So that the graph does not have to be changed during runtime of the program, the framework of the nodes is also extended by a variable. In addition to the name of the node, the orientation of the vehicle when reaching an intersection is also included. That way several subnodes are created for each node, which represent all possible orientations of the vehicle when arriving at an intersection. The map is designed grip- shaped and at an intersection never more than four roads merge. Because of that, the framework gets limited to the compass direction north, east, south and west. For the cost of the edges of the graph, travel time between nodes while driving with the maximum allowed speed is used in this implementation. There are cases where a shorter path is required, but the fastest way is usually preferred. Another advantage of using the fastest route is that the different speed zones on the map can also be included. While for the shortest distance the pure route between two nodes is enough, the required time must be calculated for the fastest route. Only subnodes themselves can be selected as start and destination points. Therefore, a software solution has to be developed which allows using coordinates instead of the subnodes. To achieve this, the entire map is divided into individual polygons, which are stored in the class of the graph. The result can be seen in Fig. 4. Figure 4. Polygons on the map If the current position of the vehicle is read out for the start of a navigation, a function checks whether it is within one of the created polygons