Path Planning

The path planner decides the path for a parallel park manoeuvre.

About myself

I am a final year Automotive technology master student at TU/e, working on my graduation project on path planning. When path planning for my thesis gets stressful, I enjoy doing the same for fun with the ATeam. If I am not path planning or worrying about bad localization data, I enjoy hanging out (sometimes literally) at the bouldering wall at SSC or spending time with my friends.

“If the path be beautiful, let us not ask where it leads.”

Anatole France

My project in short

Let’s assume you are standing in a room and it is scattered with things randomly. Your goal is to get from where you are in the room to the door, without touching anything. Also, you are lazy and would like to get to the door using as little energy as possible. For a computer, the best way to do this is to break the area of the room down to small squares, each square just big enough to fit you. Then use path planning algorithms like A-star (Think shortest possible path. In fact it is so short that it is named after ‘A’ star) to decide which boxes you should step into to get to the door, but with the least effort. But what if you are a car and can’t turn around like us humans do? By making the boxes as big as a car and then driving left, right and straight from the starting point, we can estimate where the car will end up in the next square and which direction it will face. Using this information and a slightly more complicated A-star we can now decide how the car should steer to avoid all the things it does not want to touch (like other cars or the occasional chicken crossing the road) and could still go from where it was to where it wants to be.

A technical explanation for the engineers

The algorithm we employ to plan a path is an extension of the most common graph search algorithm A-star (A*), which, depending on the how it is set up, can ensure that one can find the shortest path between two points. The extension, called Hybrid A-star (HA*) was first adopted in the 2007 DARPA Urban Challenge and has since gained much fame for being one of the fastest algorithms for path-planning with cars. A key difference between the two is that A* searches a discrete space and consequently the path is discrete and often not realisable by a car, whereas HA* still searches a discrete search space but saves the continuous state transition that the vehicle would travel between these discrete states.

In HA*, the search space is usually 3-dimensional discretized with respect to the position (x, y), and the orientation (θ) but still takes into account the continuous nature of the search space representing the real world. This is achieved by using the following set of 6 precomputed motion primitives to determine reachable states.

Drive forwards while:
1. Steering left
2. Steering right
3. Not steering

And drive reverse while:
4. Steering left
5. Steering right
6. Not steering

The continuous position which a motion primitive arrives at is stored alongside the discrete position in the corresponding cell. This is critical to ensuring that the path is drivable since a vehicle model is used to conduct the motion primitives. After generating the motions, each position is evaluated for how-far it is from the start and how-close is it to the end and one with minimum sum of the two is chosen and its 6 successors generated again. This is repeated until one of these successors is the position we want the vehicle to reach and at which point we have a path.