This is a guest talk for course 6.S094: Deep Learning for Self-Driving Cars taught in Winter 2017.

Course website: https://selfdrivingcars.mit.edu
Contact: deepcars@mit.edu

Playlist: https://goo.gl/SLCb1y

Links to individual lecture videos for the course:

Lecture 1: Introduction to Deep Learning and Self-Driving Cars
https://youtu.be/1L0TKZQcUtA

Lecture 2: Deep Reinforcement Learning for Motion Planning
https://youtu.be/QDzM8r3WgBw

Lecture 3: Convolutional Neural Networks for End-to-End Learning of the Driving Task 
https://youtu.be/U1toUkZw6VI

Lecture 4: Recurrent Neural Networks for Steering through Time 
https://youtu.be/nFTQ7kHQWtc

Lecture 5: Deep Learning for Human-Centered Semi-Autonomous Vehicles 
https://youtu.be/ByZF8_-OJNI

CONNECT:
- If you enjoyed this video, please subscribe to this channel.
- AI Podcast: https://lexfridman.com/ai/
- Show your support: https://www.patreon.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Twitter: https://twitter.com/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Slack: https://deep-mit-slack.herokuapp.com

First, we have shirts, and we'll give those out tomorrow and Friday, if you're here for the shirts.

If you're here for the knowledge, today our speaker is Sertac Karaman.

He is a professor here at MIT in the Aero-Asteroid Department.

He builds and studies autonomous vehicles that move on land and in the air.

That includes ones that have 18 wheels and 2 wheels and everything in between, robots that move fast and aggressively and robots that move slowly and safely.

He takes both the formal optimization-based approach and the data-driven deep learning approach to robotics.

He's a mentor to me and many other researchers here at MIT and beyond.

And while he is 1 of the leading experts in the world in building autonomous vehicles, for the nerds out there, he still programs.

He programs on a Kinesis keyboard, uses Emacs, which is how you know he's legit.

So please, thanks, please give a warm welcome to Sertac.

I really had the pleasure to work with Lex for some time.

And it seems like this class is him and the TAs have put together some amazing class.

He gave me this title, Past, Present, Future of Motion Planning or something.

Hopefully, that's not quite exactly what you're expecting.

So I took a whole bunch of slides from different talks and put them together.

And I am hoping to just kind of go through all as much as I can to tell you some of the interesting things, I think, in the domain that's happening and touch upon motion planning at some point.

Maybe a good starting point would be to tell you a little bit about my background.

It is exactly a decade, probably today, that I shook John Lennart's hand, who you've met before, I shook John Lennart's hand as a graduate student and joined the DARPA Urban Challenge team.

We worked through it with a number of people.

And at the time that we were doing these kind of things, back in the day, it was an academic project.

You can look at the DARPA Urban Challenge teams and you'll recognize they're all university teams, at least all the finishers.

And it came from an academic project to the thing that's going to change the world in 10 years.

So I hope to give you a bit of a history and some thoughts on that as well.

We built these beasts that I'm going to talk to you about a little bit.

I wonder if John Leonard talked at all, but I'll give you some details.

This was our entry to the DARPA Urban Challenge.

It was a Land Rover LR3 that we made autonomous that navigated through that course, and it was 1 of the 6 finishers.

A number of my friends went out and they did their own careers with a number of others.

We built a number of other autonomous vehicles.

1 thing that we have done that I was kind of doing, that I was the motion planning lead for, was this autonomous forklift.

It was a forklift that you could literally take a megaphone and speak to.

You could say forklift go to XYZ and it would go to that location.

Here it's trying to go to receiving which happens to be an area where trucks pull up with pallets on it so that you can kind of pick these palettes up and you can put a mouse back.

It beams that camera image to a handheld tablet device made by Nokia.

Back in the day, there was a company called Nokia.

They would make these phones and handheld devices so you could see what it's seeing.

You would circle so you didn't have tapping back then.

But you get these pen gestures, you could circle something and the thing would scan it and take a look at it.

So you know, let me just kind of go through this because it's kind of a bit slow So it'll scan through the palette it'll pick it up but 1 thing I would like to show you guys is that once that's done you can You can also talk to a tablet the tablet would recognize your voice and then it would command the robot to do that kind of thing.

This was before autonomous cars, before iPhone, before, I don't know, Alexa, before Siri, and things like that.

So I spent a couple of years doing this type of project that really shaped up my PhD thesis.

And later when I started as a faculty, I also worked on a number of things.

We built autonomous golf carts in Singapore's NUS, National University of Singapore campuses, to go there and do mobility on demand and so on.

The 1 thing that I ended up doing there was throughout these projects I focused mainly on motion planning that you were expecting.

The 1 algorithm that I was working on was called rapidly exploring random tree.

So you're starting in the middle of, So this is the area that you're looking at.

There is that orange dot that you're starting from.

You want to go to the magenta goal region.

You want to find the path that starts from the initial condition, goes to the goal.

That's the very basic motion planning problem.

Turns out this problem is computationally pretty challenging, especially as the number of dimensions of this process is 2 dimensional.

But if you increase the number of dimensions, you can prove that any complete algorithm, meaning any algorithm that returns a solution when 1 exists and returns failure otherwise, will scale exponentially.

So at some point you're going to run out of memory or time to do these things.

The algorithm that I was working on was called Rapidly Exploring Random Tree.

Every time you put like a random sample, you connect it to the nearest node in a tree of trajectories that you're building, and in this way you sort of rapidly explore the state space to find a whole bunch of paths.

Some of these paths may reach the goal, so that's the path that you pick.

As you can see, it's just sampling the environment, trying to build this set of trajectories that don't collide the obstacles.

If your trajectory collides with an obstacle, you just kind of delete it, and you move on with other samples, and then you would build this kind of a tree, okay?

It's an algorithm that's kind of pretty widely used, and it goes well beyond these kind of simple cases.

For example, in our urban challenge kind of entry, we were using this algorithm.

So here you're seeing the algorithm in action.

So we're trying to park at a location during what DARPA called the NQE event.

So you can see a whole bunch of cars that our vehicle is seeing generating this map.

Red are obstacles, black is the drivable region.

So that's a set of trajectories that are generated by the robot, by the RRT algorithm.

So as you can see, the trajectories are going back and then going towards the obstacles.

So it's just generating these trajectories, picking the best 1.

So we've used this algorithm throughout the race.

So you can see the performance as it's running.

So this is a video that's made about 30 times faster, kind of showing you how the thing works.

When we switched to the forklift kind of algorithm, Forklift platform, I started working on this, and the 1 thing that we realized is that the forklift tries to go here to park in front of a truck, and it finds this trajectory.

At some point, it discovers there's an obstacle here, and it finds this looping trajectory, and it never gets out of that loop.

You would think that it's trying to minimize the path length, so you would think that it would be easier to come up with something that just kind of turns left and aligns, but it turns out that once you have that loop, even if you add more samples to it, you're stuck with that loop.

And So you would never improve this type of trajectory.

So back in the day, Professor Seth Teller, who passed away unfortunately a couple years ago, but he really pushed me.

He was telling me this doesn't work, and every time it just makes this loop right in front of the army generals who are the sponsor, and it just looks ridiculous, you need to fix this kind of thing.

And trying to find a fix for it, we realized that the algorithm actually has some fundamental flaws in it.

So specifically, we were able to kind of write down a formal proof that the RRT algorithm actually fails to converge to optimal solutions.

So you would think that if you had more samples, you would get better and better trajectories.

But it turns out that the first few trajectories that you found, it just constrains you.

So it closes the space that you want to search.

Your bad trajectory is kind of good enough.

We were able to come up with another algorithm that we called RRT-STAR, which just does a little bit more work, but guarantees asymptotic optimality, meaning it will always converge to optimum solutions.

And the computational difference between the 2 is very little.

If you were to run them side by side, RRT star tree would look like this.

What it's doing is it's just looking at the paths locally, and it's just kind of correcting them locally just a little bit.

And that little bit correction is enough to converge to globally optimal trajectories.

So that turned out to be my doctoral thesis back in 2011, and we applied it to a number of things.

Imagine a race car coming into a turn, wants to turn very quickly, generates these trajectories.

So the right thing to do is to kind of slow down a little bit, start skidding, hit 1 end of the road, now start speeding up and go as fast as possible so that you hit the other end of the road and you complete the turn.

These kind of things would come out just naturally from the algorithm.

Okay, you wouldn't have to program, you have to do these kind of things, but you just run the algorithm and this is the best trajectory it finds.

It would be impossible to get something like this from an RRT.

We applied it to a number of other robots as well.

I don't know, like PR2 type robots or these autonomous forklifts and got good results out of it.

So that kind of maybe gives you a bit of an idea of my background, meaning like my graduate school experience a little bit and the PhD.

Let me kind of tell you a bit quickly what my research group does.

So I always say sort of, so we do a lot of things in a fortunate and unfortunate way, so it's hard to find the focus sometimes, admittedly.

But I usually tell people that we work on autonomous vehicles.

The problem is quite interesting, both at the vehicle level, meaning how are you going to build these autonomous vehicles individually.

And also interesting at a systems level, when you think about it, most of the autonomous vehicle is most valuable if you put them into a system that they can work.

So a system, autonomous vehicles would be, for example, this Kiva system scenario.

You know, nowadays you buy something from Amazon, the way it's you buy 2 books, the way it's packed is that books are brought by robots to a picker and the picker just puts them into the same box and sends it to you.

So this is done by 500 autonomous vehicles for example, That would be a good example of a system.

Another 1 is that there are ports around there in the world that are working just completely with autonomous vehicles and cranes.

If you project a little bit forward, you can think maybe you can have drone delivery systems, and they maybe don't have enough battery, so they have to relay packages to 1 another so you need to build a system of autonomous vehicles or if you have I don't know like autonomous cars maybe it's best to use them in like an uber like scenario so you can have autonomous taxis that they can work together and such.

So let me tell you a bit more on the vehicle level problems and the system level problems, some of the crazy things that we try to do.

On the vehicle level, we're interested in all aspects of both perception and planning.

Usually challenges are sort of either complexity or either computational complexity, so it's very hard just computationally, so you really need to annoy it, or it's just, the system becomes very complex, so you need to figure that out.

We're, for example, recently motivated by really fast and agile kind of vehicles, how we can build that.

Like 1 thing that we were motivated for example is sort of like imagine there's a drone flying and you want to catch it in the fly.

So you know, it turns out that Netherlands police is, some people fly UAVs around and you somehow want to take it down.

So people train eagles and things like that.

So we thought it would be great to actually build these types of robots that we try to in our group.

So Once you start to do these kind of things, you wonder like how much I can push the boundaries of very, very agile vehicles and systems.

So here you're going to see a falcon diving for a prey.

You're going to see a goose right at the last like a split second.

So if you look at the scene from a 20 hertz camera, this is what you would see.

They do very complicated planning and maneuvering to be able to do these kind of things.

So in the research group, we look at a number of different perception problems where You have multi-agents, you have ultra-high rate cameras.

Like for example, we have drones with 200 Hertz cameras on them.

And so you're trying to understand the person that you're tracking, its dynamics, its intentions.

On the control level, you're trying to pull off really complicated maneuvers, like the 1 that you've seen in the race car, but you want to do it in real time at like a kilohertz probably.

So for example, the drones that we have actually have GPUs on them.

They fly like teraflop computers to be able to do these kind of things.

We also use them offline, like the deep learning computers that you would use normally.

You have access to things like DGX1 and so on that we use that to compute controllers, for example.

Here's an example of, I don't know, like 1 GPU drone just kind of passing through a window.

But these are the controllers that we would compute on supercomputers that we would deploy.

And on the perception side, for example, we're looking at things where you can use visual metronometry, you can just have a camera, and just look through the world from the camera and try to understand your own position So we have certain algorithms to pick the features just right so that you can do these things with just like 10 features or something Like that so that it is computationally very efficient On the systems aspects of things and when you put them together.

Yeah, so the question was, what do you mean by sort of computing the controllers?

Would you want to find the best constants?

So controllers are actually pretty complicated objects.

It has, suppose it has 6, it has actually 12 degrees of freedom, but suppose it has 6 degrees of freedom.

Suppose you discretize every dimension with 200 points, so six-dimensional position and orientation.

points, 200 to the 6, would be thousands of trillions.

If you were to write 1 byte for every point in the state, so you're looking at the state space, for every point in the state space, what's the action that I'm going to do?

If I end up at that position and orientation, what action should I do?

If you use 1 byte to write it in the memory, it would make 2.5 petabytes of this controller.

When you think about it, you don't really need, it would be very surprising if that maneuver really, to be able to describe it, like in information theoretic terms, To be able to describe it, it would be very surprising if it requires thousands of trillions of parameters.

So millions, maybe, but trillions, seriously?

So what we do is, to be able to compute these things, we take very simple controllers, like for example, 0.

We compress them, like as in data compression.

And then we work on the compressed versions.

And then that compressed version grows up to a level that comes down to something like 2 megabytes.

That's probably essentially what you would need, rather than 3 terabytes, for example.

We use kind of singular value decomposition type techniques to do compression.

You may have done the same thing using images, for example.

If you compress an image, JPEG, you save an order of magnitude.

If you compress video, you save 2, 3 orders of magnitude because video is 3 dimensional.

As you increase the dimensions, there's more to compress.

So when you compress this way, this saves 10 orders of magnitude, which honestly is no surprise when you think about it a little bit.

So those are the control, like the planning and control algorithms that we use.

So we compute them in, I don't know, 5 minutes.

That gives you a lookup table that's 2 megabytes you put in so that you can quickly execute it.

That lookup table is essential if you want to do a kilohertz control.

You won't be able to compute a trajectory at that rate.

That question came in, and that's the whole talk in terms of present of motion planning.

And there's a lot to do, especially in terms of agility on the systems domain as well.

This is not the kind of stuff that only stuff that we do, but I pulled up the most interesting thing, I think, maybe the most crazy thing of my hard disk.

Imagine you have a whole bunch of vehicles coming to an intersection, suppose they're fully autonomous, how would you make it so that they would pass through the intersection as fast as possible?

So if you were to really utilize algorithms that will do that, here is what I would look like.

So you would have Vehicles coming in, and you could, it looks like, so you probably don't want to sit in this vehicle.

But just sort of like, just to understand the fundamental limits of the situation, just to understand how far you can push these things.

You can see, it looks like they're getting very lucky.

But really what's happening is that they're just speeding and slowing down just so little so that they can avoid 1 another So you can actually sit down and do some math and try to understand, you know Given the dynamics like your acceleration deceleration limits how fast you can push these things Maybe it doesn't immediately apply to self-driving cars, but certainly you can use it in warehouses and things like that, which would actually improve operations quite a bit.

I wonder if any of you have seen Kiva Systems' warehouses.

You look at it, most of the robots are stopped.

Can you talk about the robustness aspects of, you know, kind of, oh, I'm doing these things.

For example, you know, like, can you control that before we end up getting back?

Is there anyone working on the robustness aspects of the control, distributed control?

Yeah, so the question is, is there anyone working on robustness aspects of distributed control?

We have looked at things from the theoretical perspective.

It turns out that, Even in this case, there's something like a critical density of these things.

So below the critical density, things are very simple.

You're going to be able to find paths, and you're going to be able to execute.

Above the critical density, things are very hard.

Like if something fails, just kind of the whole system will crash into 1 another.

And this is no surprise either, like this is kind of the physics of many, you know, just like, you see it everywhere.

I mean, it's the same thing as, I don't know, you heat this thing, there's a critical temperature, above it it looks different, below it it looks like a liquid.

You can use the same kind of thinking or theoretical arguments to come up with these types of things.

And I know that a lot of people work on specific controllers for vehicle level to guarantee robustness and so on.

Probably those are the kind of things that 1 needs to do before implementing these types of algorithms.

But in the current existing multi-vehicle setups, like Kiva systems or ports and things like that, we are far away from this kind of thing.

The main problem, some of it is control, like we don't understand the control aspects, but we also don't trust our sensors and things like that.

So probably more of the research is on the, not research, but implementation is on the sensor side, I'd say.

yeah, So we have been doing a number of other projects currently as well on autonomous vehicles.

If you're interested in any 1 of them, let me know.

I'm not going to show you videos, but let me just kind of tell you with 1 slide and a few pictures.

This was several slides, but I felt really bad.

That may sound funny, but it's actually pretty hard to test with autonomous vehicles.

So we currently have 5 of these, and we're hoping to build 30 so that we can put them in.

And they're currently in a little robot-enclosed area in Taiwan.

And they're just driving around collecting data so that we can, for example, you can feed them into deep learning algorithms.

We also have in ABI's warehouses, we have 1 of these robots.

Supposed to be kind of like, I'm sure you know of WeThink Robotics, like they make this robot arm, it's supposed to be very easy, you can interact with.

You can just talk to it, you can tell it stuff to do and it can do that.

You can show it, you can hop on it, you can do it yourself type of thing.

I am also a lead PI together with sort of working with Daniela Rus on MIT's effort with Stanford and Toyota to build safer vehicles.

And finally I'm still a PI on the MIT Singapore partnership.

See all Lex Fridman transcripts on Youtube

Sertac Karaman (MIT) on Motion Planning in a Complex World - MIT Self-Driving Cars