Reflections on Designing a Virtual Highway Path Planner (Part 1/3)

Right now it swerves like a crazy wishy-washy undecided driver and ironically too conservative at keeping its lane at the same time. But to be honest I’m just happy it navigates towards around the virtual loop several times bumping to anyone or exceeding the maximum speed, acceleration, and jerk requirements. It swerves when all the lanes are empty but is too afraid to turn even when the gap between vehicles are sufficient. It isn’t even driving near the speed limit afraid it might go over.

The first project for the third (and last!) term of Udacity’s Self-driving Car Engineer Nanodegree is a path planner. I think so far this is the most difficult project yet, as it isn’t as straightforward as our previous projects. This three-part article is about how I approached this project.

The goal is to create a path planning pipeline that would smartly, safely, and comfortably navigate a virtual car around a virtual highway with other traffic. We are given a map of the highway, as well as sensor fusion and localization data about our car and nearby cars .We are supposed to give back a set of points (x , y)in a map that a perfect controller will execute every 0.02 seconds. Navigating safely and comfortably means we don’t bump into other cars, and we don’t exceed the maximum speed, acceleration and jerk requirements. Navigating smartly means we change lanes when the car in front of us is too slow.

Outline of Contents

PART 1

• Introduction and Outline of Contents
• Design Guidelines I followed (and my Analysis Paralysis)

PART2

• Broad Overview of My Pipeline
• Data Structures

PART3

• Deciding which Behavior to Take
• Generating an Actual Path
• Something Fishy
• Converting the Path to What the Controller Understands
• Final Statement

Design Guidelines I followed

“All models are wrong but some models are useful”

— Probably George Box

“Everything should be made as simple as possible, but not simpler.”

— Probably NOT Albert Einstein

To be honest, for a long period of time I was in a state of analysis-paralysis and did not even write a single line of code. I was thinking about so many things. There were so many concepts taught to us, I wanted to consider them all.

Which data is important and which isn’t? How far into the future should I plan? Should I predict what the nearby cars are going to do before deciding what to do? What method should I use in prediction? How accurate and useful are these predictions? How many possible behaviors should I consider (e.g slow down, go fast, turn right, prepare to turn left)? For any behavior, how many paths should I consider before deciding which is the best one? If I decide to go slow, how slow? If I decide to turn left where exactly in the left? How do I make sure that my path is the best and does not violate any safety or comfort guidelines?

YAGNI” — Extreme programmers

“If it ain’t broke, don’t fix it” //Disclaimer: this does not apply to societal problems

And on top of that, the pseudo-architect in me was also talking. What data structures should I use? What classes and objects should I define? How will they interact with one another? What are the member responsibilities of each object? Does it even make sense that responsibility belongs to that object?

After some contemplation, I remembered something I read a while back by George Box, a famous statistician.

“Now it would be very remarkable if any system existing in the real world could be exactly represented by any simple model. However, cunningly chosen parsimonious models often do provide remarkably useful approximations. For example, the law PV = RT relating pressure P, volume V and temperature T of an “ideal” gas via a constant R is not exactly true for any real gas, but it frequently provides a useful approximation and furthermore its structure is informative since it springs from a physical view of the behavior of gas molecules.

For such a model there is no need to ask the question “Is the model true?”. If “truth” is to be the “whole truth” the answer must be “No”. The only question of interest is “Is the model illuminating and useful?”

I decided that I should start with a simple model with many simple assumptions and work from there. If the assumption does not work then I will then make my model more complex. I should keep it simple (stupid!).

A programmer should not add functionality until deemed necessary. Always implement things when you actually need them, never when you just foresee that you need them. A famous programmer said that somewhere.

My design principle is, make everything simple if you can get away with it.

Read: Part 1 of 3 | Read: Part 2 of 3| Read: Part 3 of 3