Planning in ISS

The planning module is a key part of self-driving vehicles, guiding the vehicle from one point to another. It has important tasks like figuring out the best overall route to the target destination (global planning) and planning vehicle’s short-term motion (local planning). The actual commands to be given to the vehicle are instead under the responsibility of the control module.

For the planning module to work, it gets information like where the vehicle is (localization) and detailed maps. Then, it decides on important details, like how fast the vehicle should go and how it should turn, so to follow the chosen roads leading to the destination. These decisions are then sent to the control module, which makes the vehicle move accordingly.

In practical terms, the planning module can be seen as the combination of two planners, operating at different detail levels. First, the global planner decides the best way to go from where the vehicle currently is to where it needs to be, like choosing the sequence of roads to use. Second, the local planner comes up with short-term plans for the vehicle to follow in real-time, especially when there are unexpected things in the way, such as lanes being temporarily closed or occupied by slow vehicles.

The table below list the global and local planning algorithms that are currently supported in ISS:

TypeInputsOutputsAlgorithmsSource
Global planner
  1. Start and goal position
  2. Map information
 Planned global path (route) A*1 / Hybrid A*2 ISS Sim
A*1 / D*3 / PSO4 ISSPA
A*1 ISS Isaac
Local planner
  1. Global path
  2. Map information
  3. Robot's dynamics and constraints
 Optimal local trajectory Motion Primitive5 / MPCC6 / TEB7 ISS Sim
DWA8 / TEB7 ISSPA
DWA8 / TEB7 ISS Isaac
Controller
  1. Target state
  2. Current state
  1. Motor speed control
  2. Steering control
 PID9 / PurePursuit10 ISS Sim
PID9 ISSPA
PID9 / Ackermann Controller / Differ ISS Isaac
RL(end2end)
  1. Target position
  2. LiDAR data
  3. IMU data
  1. Linear velocity
  2. Angular velocity
 PPO11 ISSPA
TD312

Global Planner

The task of the global planner, also called the route planner, is to find the most effective route from the current location to the desired destination, much like how conventional GPS navigation systems operate. Modern route planning algorithms are able to return an optimal route on large scale in real time, after a one-time pre-processing step13. For a more comprehensive survey, refer to the paper by Bast et al14.

In order to find the overall route from the current location to the destination, the global planner requires multiple data as input. These are high-level information about the world, such as:

  • the position of the start point and of the end point, such as their GPS coordinates;
  • the map information, such as the topology of the road network;
  • possible permanent obstacles; and
  • optionally, information about the traffic conditions.

Information about permanent obstacles and traffic conditions can be used by some of the algorithms to optimize the choice between different possible routes, for instance to reduce the expected trip length or to avoid specific road where specific vehicles are forbidden. This can happen, for instance, when the selected route uses roads having specific limits on the weight of the vehicle crossing a bridge or on the size of the vehicle entering a tunnel.

The output generated by the global planner is a path or a series of waypoints bridging the start and destination positions, while sidestepping any permanent obstacle. This means that the global planner faces many challenges while generating the route, since it has to consider changing road situations, possibly the real-time traffic details when choosing among multiple routes that are available to reach the destination while ensuring the chosen route is admissible, safe and efficient.

Local Planner

The main task of the local planner is to dictate the vehicle’s overarching behavior, from decisions about lane switches, overtaking, yielding, to making turns. It is also responsible to guarantee a smooth experience of the vehicle’s passengers, for instance by avoiding sharp steering/braking maneuvers. In literature it is common to find alternative names for the local planner or of some of its tasks, such as behavior planner and motion planner. Nowadays, the local planner often incorporates the interaction between the ego vehicle and other agents on the road, such as other vehicles15.

To achieve its goal, the local planner uses static information from multiple sources, such as

  • the designated route obtained from the global planner;
  • detailed map information; and
  • vehicle’s structural information.

It also uses dynamic information from other source, such as

  • data about neighboring vehicles and pedestrians (obtained from LiDAR, radar, cameras, etc.);
  • traffic light information; and
  • other pertinent environmental data.

These data are combined together and analyzed to generate the macro-level directives such as “shift to the left lane”, “trail the vehicle in front”, or “get ready to turn right” and the corresponding coarse trajectories, having a short-time validity. These directives are then refined to an optimized trajectory, detailing the vehicle’s state over a specified time frame; such an optimized trajectory includes specific driving instructions to be provided to the control module to be actually executed by the vehicle.

In making its decisions, the local planner needs to address multiple issues, such as anticipating the intentions and forthcoming actions of surrounding drivers and pedestrians, adopting a safe decision formulation in intricate scenarios, and navigating uncommon edge cases. It also needs to craft trajectories that avoid collisions and are streamlined and smooth, manage noisy and uncertain data from sensors, and perform real-time trajectory mapping to take into consideration possible differences between the planned trajectory and the actual trajectory followed by the vehicle.

References

  1. Nilsson, N. J., Principles of Artificial Intelligence, Tioga Publishing Company, 1980. ↩ ↩2 ↩3

  2. Dolgov D, Thrun S, Montemerlo M, et al. Path planning for autonomous vehicles in unknown semi-structured environments. The International Journal of Robotics Research, 2010, 29(5): 485-501. ↩

  3. Stentz A. Optimal and Efficient Path Planning for Partially-Known Environments. IEEE International Conference on Robotics and Automation (ICRA). IEEE, 1994: 3310-3317. ↩

  4. Kennedy J, Eberhart R. Particle swarm optimization (PSO). IEEE International Conference on Neural Networks (ICNN). IEEE, 1995: 1942–1948. ↩

  5. Werling M, Kammel S, Ziegler J, et al. Optimal trajectories for time-critical street scenarios using discretized terminal manifolds. The International Journal of Robotics Research, 2012, 31(3): 346-359. ↩

  6. Brito B, Floor B, Ferranti L, et al. Model predictive contouring control for collision avoidance in unstructured dynamic environments. IEEE Robotics and Automation Letters 4.4 (2019): 4459-4466. ↩

  7. Rösmann C, Hoffmann F, Bertram T. Kinodynamic trajectory optimization and control for car-like robots. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2017: 5681-5686. ↩ ↩2 ↩3

  8. Fox D, Burgard W, Thrun S. The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33. ↩ ↩2

  9. Rajamani R. Vehicle dynamics and control. Springer Science & Business Media, 2011. ↩ ↩2 ↩3

  10. Coulter R C. Implementation of the Pure Pursuit Pat Tracking Algorithm. Carnegie Mellon University, 1992. ↩

  11. Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. ↩

  12. Fujimoto S, Hoof H, Meger D. Addressing function approximation error in actor-critic methods. International conference on machine learning. PMLR, 2018: 1587-1596. ↩

  13. Paden B, Čáp M, Yong S Z, et al. A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Transactions on intelligent vehicles 1.1 (2016): 33-55. ↩

  14. Bast H, Delling D, Goldberg A, et al. Route planning in transportation networks. Algorithm engineering (2016): 19-80. ↩

  15. Ding W, Zhang L, Chen J, et al. Epsilon: An efficient planning system for automated vehicles in highly interactive environments. IEEE Transactions on Robotics 38.2 (2021): 1118-1138. ↩