Let’s admit it: self-driving technology is continuing its expansion globally by bringing to life bold technologies such as sophisticated path planning algorithms, precise geolocation, and deep learning capabilities. Autonomous driving is creating millions of possibilities for previously unrelated businesses – OEMs, software vendors, and Tier 1 companies – to find new ways for win-win cooperation.
Over the past decade, Intellias has been partnering with global location-based services (LBS) and automotive solutions providers and has learned that path planning for autonomous vehicles is crucial to autonomous driving and is, in fact, the most in-demand technology among companies that develop self-driving vehicles.
Effective path planning algorithms are what make autonomous driving genuinely feasible, safe, and fast.
This article will discuss how path planning algorithms for autonomous vehicles work, which methods manufacturers and software developers apply to make it accurate, and most intriguingly, what business opportunities this technology can offer you besides safe driving. How about the Hyperloop as an alternative for your next commute home or your trip from coast to coast? Get ready to maneuver at hyper speed without leaving the atmosphere.
Definition of path planning for autonomous vehicles
Autonomous car planning and decision making for self-driving cars in urban environments enable transport to find the safest, most convenient, and most economically beneficial routes from point A to point B. Finding routes is complicated by all of the static and maneuverable obstacles that a vehicle must identify and bypass. Today, the major path planning approaches include the predictive control model, feasible model, and behavior-based model. Let’s first get familiar with some terms to understand how these approaches work.
- A path is a continuous sequence of configurations beginning and ending with boundary configurations. These configurations are also referred to as initial and terminating.
- Path planning involves finding a geometric path from an initial configuration to a given configuration so that each configuration and state on the path is feasible (if time is taken into account).
- A maneuver is a high-level characteristic of a vehicle’s motion, encompassing the position and speed of the vehicle on the road. Examples of maneuvers include going straight, changing lanes, turning, and overtaking.
- Maneuver planning aims at taking the best high-level decision for a vehicle while taking into account the path specified by path planning mechanisms.
- A trajectory is a sequence of states visited by the vehicle, parameterized by time and, most probably, velocity.
- Trajectory planning or trajectory generation is the real-time planning of a vehicle’s move from one feasible state to the next, satisfying the car’s kinematic limits based on its dynamics and as constrained by the navigation mode.
A continuous search of space and corridors determines successful autonomous car path planning
Motion planning for autonomous vehicles becomes possible after technology considers the urban environment in a way that enables it to search for a path. Put simply, the real-life physical environment is transformed into a digital configuration or a state space. Path planning technology searches for and detects the space and corridors in which a vehicle can drive.
Path planning for autonomous vehicles becomes possible after technology considers the urban environment in a way that enables it to search for a path.
These are the major path planning algorithms used for finding corridors and space:
- The Voronoi diagram (a) algorithm generates paths that maximize the distance between a vehicle and surrounding obstacles.
- The occupancy grid (b) algorithm works similarly to the Voronoi diagram, though risk and feasibility are calculated primarily by considering the presence of obstacles and lane and road boundaries.
- Whereas the occupancy grid consists almost exclusively of a grid with the obstacle’s position, with the cost maps (c) algorithm, the higher cost of a cell results in its more intense representation on the map.
- The state lattices (d) algorithm uses a generalization of grids. Grids are built by the repetition of rectangles or squares to discretize a continuous space, while lattices are constructed by regularly repeating primitive paths that connect possible states for the vehicle.
- The driving corridors (e) algorithm recreates continuous collision-free spaces, bounded by lanes and other obstacles between which the vehicle is expected to drive. Driving corridors algorithms use data from digital maps built by Simultaneous Location and Mapping (SLAM) models.
Old fashioned mathematics behind autonomous car path planning
Let’s add a little bit of rocket science to autonomous driving path planning. The model predictive control approach solves a finite-time constrained optimal control problem in a receding horizon. Path planning can, therefore, be formulated as a nonlinear optimization problem:
In this formula, N marks the prediction horizon while M is the number of lanes on the roadway. Equation 1b is the constraint imposed by the vehicle kinematics; equation 1c constrains the feasible set of the state, which considers the actuator limits of the vehicle; equation 1d enforces collision avoidance between the vehicle in question and surrounding vehicles. Using this mathematical model, the predictive control algorithm can define the most feasible way to change lanes, avoid collisions, and complete other sophisticated maneuvers.
How does path planning for autonomous vehicles work?
After the route planner generates a path through the road network, the technology’s behavioral layer evaluates the surrounding environment and generates the most appropriate motion specification for the trip. Then the motion planner elaborates the feasible driving mode to meet the specification. Finally, the feedback control adjusts the mode in real-time to correct errors and overcome obstacles on the road.
After the route planner generates a path through the road network, the technology’s behavioral layer evaluates the surrounding environment and generates the most appropriate motion specification for the trip.
Smooth local path planning for autonomous vehicles is no longer a matter of simply choosing the shortest path from the starting point to the destination. Today, path planning technologies encompass a wide range of aspects to calculate the safest, most convenient, and most efficient route. Put simply, path planning self-driving car uses on a daily basis is based on two major elements: behavior prediction of maneuverable objects and behavior planning for the vehicle itself.
Predicting the behavior of maneuverable objects
Multiple-model path planning algorithms for maneuvering target tracking are used to predict the behavior of all dynamic objects in the space and corridor, and then based on this, to predict the trajectory of each object to react fast with ADAS functionality. These algorithms evaluate multiple possible maneuvers simultaneously for each object, then correlate them with updated over-the-air on-road observations.
Eventually, the algorithm defines the probability of each potential maneuver by the object. High-probability maneuvers are afterward used to build the expected trajectory. After trajectories are defined, the path planning technology considers the most appropriate vehicle behavior.
Planning vehicle behavior to get the safest path
Behavior planning for vehicles encompasses driving efficiency and the balancing of safety and comfort. Driving efficiency means determining the best lane to reach the destination promptly while comfort means getting to that lane feasibly and safely. Ranking lanes and feasibility checks are therefore the two core elements underlying vehicle behavior planning.
With regard to lane ranking, the algorithm is led by three main principles.
- First, the fewer lane changes, the better.
- Second, the larger the distance to the moving object ahead, the better the score for maneuvers.
- Third, the greater the velocity of the object ahead, the faster the car can drive in the lane.
After each possible lane is ranked, their feasibility is defined. The scheme below shows how the algorithm defines feasibility.
A hierarchical framework for path planning self-driving car would use
Applying the hierarchical model for path planning enables autonomous vehicles to complete long-term missions and reduce the workload of motion planning. In other words, the hierarchical model optimizes the work of path planning technologies.
For each layer of the hierarchy architecture, the input higher-level mission is decomposed into sub-missions and then passed to the next level down. The hierarchical model helps to resolve many complicated problems, yet it might slow down the work of a vehicle’s feedback control and complicate the performance of sophisticated maneuvers.
A parallel framework for autonomous car path planning
Compared with the hierarchical model, the processes in the parallel framework for path planning are more independent and can proceed simultaneously. With this framework, each controller has dedicated sensors and actuation mechanisms.
Using the parallel framework has some benefits. First, the controllers are running at a high frequency, making them safe and stable. Second, the controllers achieve a high level of smoothness and performance. Third, the model is relatively inexpensive and doesn’t require the use of complicated motion planning devices.
Still, for some purposes, the hierarchical model remains more efficient. For instance, with a parallel framework for path planning, a vehicle may hardly merge into a lane with slower traffic while a car’s intended movements aren’t consented to by its speed controller.
Is autonomous car path planning simple or not?
Developers have been quite successful in building technologies that provide feasible path planning for autonomous vehicles from the viewpoint of traffic intensity, safety, and economic relevance. But the market demands for path planning go far beyond these basic features.
Automatically generated routes for both human-driven and self-driving vehicles are expected to encompass a wide range of points of interest (POIs) that have little in common with the technical aspects of the drive. For autonomous vehicles as well as for regular cars, POIs include charging stations, battery replacement points, and repair centers.
If there are passengers in a vehicle, they’ll probably want something more to make the trip comfortable. Path planning technology can look for cafés and restaurants close to the route so drivers and passengers don’t miss a meal. In addition, path planning technology can evaluate the best ways to pick up passengers or carry freight if necessary. Sophisticated smart planning is about to bring a plethora of new opportunities to previously unrelated OEMs, software vendors, and Tier 1 companies.
Path planning has the potential to include an airline-speed option
The use of advanced path planning technologies isn’t limited to self-driving vehicles. It’s also essential for projects at the forefront of logistics like Hyperloop. Probably you’ve heard of Elon Musk’s plan to build a multi-state underground tunnel connecting the major cities of the East Coast. This idea will hardly become reality without sophisticated path planning software.
The Hyperloop project aims at transporting pods with people or cargo through steel tubes at 700 miles per hour. With its huge vacuum pumps and magnetic levitation, Hyperloop is likely not only to become the fastest form of transport but also to be cheaper, safer, and better for the environment than planes, cars, or trains. The diagram below shows the energy cost per passenger for a journey between Los Angeles and San Francisco.
The idea of airline-speed connections through near-vacuum tubes may sound like fantasy. But recent Hyperloop prototypes demolish the skepticism. At CES 2018, Virgin Hyperloop One presented an app that lets you plan Hyperloop trips in the same convenient way you plan flights and car trips today. Virgin’s path planning tool was developed in cooperation with the mapping and navigation specialists from HERE Technologies.
Virgin Hyperloop One presented an app that lets you plan Hyperloop trips in the same convenient way you plan flights and car trips today.
The Hyperloop app will enable users to book a seat on the Hyperloop in addition to scheduling Uber or Lyft rides. Currently, HERE Technologies’ mobile software kit includes mapping and navigation data from more than 130 countries, public transit information for almost 1,300 cities, and 3D indoor and venue maps.
Hyperloop brings new opportunities for alternative path planning
The promised simplicity and accessibility of Hyperloop gives reason to believe that the technology will achieve mass use in a few years. Interest in Hyperloop among developing markets proves that there’s no alternative to fast, safe, and environmentally friendly transportation.
Ukraine’s Minister of Infrastructure Volodymyr Omelian has recently announced the launch of a Ukrainian prototype Hyperloop. The HypeUA project will be implemented in three phases, so the first facility tests are expected to take place in 2 to 3 years. The project’s launch means that a plethora of logistics opportunities will open up for local and international businesses. It will also increase a demand for advanced path planning solutions.
Without predictive, feasible, and behavior-based planning, the potential of autonomous vehicles may hardly be unleashed to its full extent. Path planning is an integral element of transportation projects at the forefront of technology, including the Hyperloop One project. Manufacturers that introduce the most efficient software planning solutions will gain the upper hand and become trendsetters within the autonomous driving industry. Using smart path planning for autonomous vehicles, business spots prioritized on automatically generated routes will also increase profits and revenues.
Intellias experts know how to benefit from the use of path planning technologies. Contact us and take a step toward the future of autonomous, prompt, and safe transportation.
