Dynamic Vehicle
Rerouting Using
Map Information & LIDAR
Path Planning & Navigation


Contact Information

Roger Lopez
Manager
Autonomous Systems & Controls
(210) 522-3832
rlopez@swri.org

Image: The multi-lane route class is used to represent not only the shortest path to the destination but also all of the data pertaining to the different segments (individual lanes of a particular roadway) included in that shortest path.

The multi-lane route class is used to represent not only the shortest path to the destination but also all of the data pertaining to the different segments (individual lanes of a particular roadway) included in that shortest path.

 

Image: The vehicle currently detects other objects in its environment using scanning LIDAR.

The vehicle currently detects other objects in its environment using scanning LIDAR.

 

Image: Lane changing for obstacles diagram.

Lane changing for obstacles diagram.

 

Image: In the case where all of the lanes are blocked in one direction of a segment, the CIM will go into the 3-point turn behavior.

In the case where all of the lanes are blocked in one direction of a segment, the CIM will go into the 3-point turn behavior.

 

Image: The vehicle will move forward at its minimum turn radius until it reaches the edge of the furthest opposing lane. The vehicle will then back up at its minimum turn radius to the right to a minimum distance required to complete the turn in the next forward move or until it reaches the other edge of the roadway.

The vehicle will move forward at its minimum turn radius until it reaches the edge of the furthest opposing lane. The vehicle will then back up at its minimum turn radius to the right to a minimum distance required to complete the turn in the next forward move or until it reaches the other edge of the roadway.

 

Image: Once the vehicle is in the furthest opposing lane and has completed the 3-point turn maneuver, the CIM sends a message to the Route Management Node requesting a new shortest route to the previously designated destination.

Once the vehicle is in the furthest opposing lane and has completed the 3-point turn maneuver, the CIM sends a message to the Route Management Node requesting a new shortest route to the previously designated destination.

A commercially available 2006 Ford® Explorer was retrofitted by Southwest Research Institute (SwRI) with the sensors, actuators, and computing hardware needed to sense the state of the world and make intelligent decisions based on that information. For a driverless vehicle to autonomously negotiate traffic, navigation tasks range from steering and speed control to negotiating complex urban environments with stop signs, traffic lights, other vehicles, and pedestrians.

One of the many required features is rerouting the vehicle when conditions do not match the original map, from simply changing a lane to avoid an obstacle to changing the planned route when the original route is blocked.

Multi-Lane Route Class

The multi-lane route (MLR) class is used to represent not only the shortest path to the destination but also all of the data pertaining to the different segments (individual lanes of a particular roadway) included in that shortest path. The information in the MLR is populated at the time of the shortest route calculation and passed to the Central Intelligence Module (CIM) for use in real time route decision making for behaviors such as passing slow moving vehicles and 3-point turns in the case of blocked paths.

General Route Following

The MLR is used by the CIM in situations where obstacles are not encountered to simply manage if lane changes are required to make a left or right turn to continue on the shortest route to the destination. At the time of shortest route calculation, roadways with multiple lanes are simplified to include a minimal lane change distance to any point on the network where one segment can be accessed from another (i.e., a left or right turn). This simplification allows for faster calculation of the shortest route while still enforcing the physical vehicle limitations pertaining to the minimum turn radius.

The CIM will implement a lane change over a longer distance based on speed if it is possible to provide for a smoother, more comfortable lane change. If there is not enough distance for a longer lane change, the vehicle will have to slow down.

Lane Changes for Obstacles

In addition to using the MLR to follow the predetermined route, the CIM utilizes the MLR to determine if and when the vehicle should perform lane changes when obstacles are detected. The vehicle currently detects other objects in its environment using scanning laser incident detection and ranging (LIDAR) sensor. If an object is located and determined to be on current desired path of the vehicle, the vehicle must then react to that obstacle. At this point, the CIM looks at the speed of the obstacle and the remaining distance on the path to determine the best course of action. If the obstacle is not in the lane of the segment that would ultimately be required to exit to another segment, the CIM will simply force the vehicle to change lanes earlier than it would if it had determined that a route lane change was needed to reach that exit location due to the remaining distance on that segment.

If the obstacle is determined to be stationary and in the lane needed to exit the segment the CIM analyzes the MLR for possible courses of action. First, the CIM determines if there are adjacent lanes to the current lane traveling in the same direction to either the right or the left. If there are, the vehicle will determine if it can change into a lane, pass the obstacle, and have enough room to change lanes back into the current lane to reach the exit from that segment. If so, the vehicle will modify the route to change lanes around the obstacle and then change back after the obstacle. If there is not enough distance or the lane is blocked, the vehicle will check for other lanes that might be used to travel around the obstacle and reach the goal. If no lanes are found that will get the vehicle back to the lane with the exit, then the vehicle will go into the 3-point turn behavior. If both lanes adjacent to the current blocked lane are available, the vehicle will select the lane that provides the shortest distance to the exit, including lane changes.

In the case where the obstacle is in the current lane of the vehicle and is moving along that lane, the CIM additionally takes the speed of that obstacle into account to determine how it will react. In the case where the obstacle is moving faster than the desired speed of the vehicle, the vehicle will continue on its current course because a collision is not imminent. If the obstacle is moving at a speed slower than the desired speed of the vehicle, the CIM will look at the difference between the speed of the obstacle and vehicle and then determine if there is enough distance to move around the obstacle, assuming it will maintain its current speed, and move back into the lane in front of the obstacle before it reaches its exit.

In addition to this distance check, the checks performed in the case where the obstacle is stationary listed above are also performed. If there is not enough room to pass the obstacle and make it back in the lane for an exit, the vehicle will slow down and follow the obstacle at its current speed. If the CIM determines that it can pass a vehicle based on the assumption that the obstacle will travel at a fixed speed and changes lanes then the obstacle speeds up, the vehicle will slow down if there is not enough room to pass and pull back in the lane behind the obstacle after it passes.

Three-Point Turns

In the case where all of the lanes are blocked in one direction of a segment, the CIM will go into the 3-point turn behavior. In this behavior, the vehicle will first back up, if there is nothing behind it, to get a better view of all the lanes to ensure that they are blocked. Additionally, if one of the further lanes is actually open, the vehicle will have enough room to change lanes to get over to that lane. Backing up will also give the vehicle enough room to perform a 3-point turn if it has gotten too close to the obstacle in front of it. If, after backing up, the vehicle still determines that all of the lanes in its current direction are blocked on that segment, the CIM will then use the data in the MLR to locate the lanes on the segment that travel in the opposing direction. These opposing lanes are then checked for moving obstacles approaching the current position of the vehicle and stationary objects within the area where the 3-point turn would occur. Once the opposing lanes are found to be clear, the vehicle will then check to see if the distance from the current lane to the furthest opposing lane is greater than two times the minimum turn radius of the vehicle. If this is the case, then the vehicle will perform a U-turn into the furthest opposing lane. In the case where the furthest lane is closer than two times the minimum turn radius, the vehicle will start a 3-point turn maneuver. In this maneuver, the vehicle will move forward at its minimum turn radius until it reaches the edge of the furthest opposing lane. The vehicle will then back up at its minimum turn radius to the right to a minimum distance required to complete the turn in the next forward move or until it reaches the other edge of the roadway. After that, the vehicle will move forward with the turn radius required to end up in the furthest opposing lane with a heading that matches that of the lane. If the vehicle cannot reach this heading on this move, which might be the case for narrow two-lane roads, the vehicle will perform as many back and forth maneuvers as needed until it reaches the desired state.

Once the vehicle is in the furthest opposing lane and has completed the 3-point turn maneuver, the CIM sends a message to the Route Management Node requesting a new shortest route to the previously designated destination. In this message, the CIM excludes all of the points that were blocked that triggered the 3-point turn to prevent paths going through those points from being included in the new route. Once this new route is determined, a new MLR is generated for the new shortest path and sent to the CIM to start following again.

Related Terminology

dynamic vehicle  •  autonomous traffic negotiation  •  multi-lane route  •  laser incident detection and ranging sensor  •  LIDAR  •  3-point turn  •  central intelligence module  •  lane changing obstacles

Benefiting government, industry and the public through innovative science and technology
Southwest Research Institute® (SwRI®), headquartered in San Antonio, Texas, is a multidisciplinary, independent, nonprofit, applied engineering and physical sciences research and development organization with 9 technical divisions.

04/15/14