From Looping Forklifts to Self-Driving Cities: Sertac Karaman on Motion Planning

Karaman opens with his own history. Almost exactly a decade earlier he joined MIT's DARPA Urban Challenge team as a graduate student, and he was later the motion planning lead for an autonomous forklift that responded to voice commands and pen gestures on a handheld tablet. He points out that this came before the iPhone, Siri and Alexa.

His main tool was the rapidly exploring random tree, or RRT. The basic motion planning problem is to find a collision-free path from a start to a goal among obstacles, and any complete algorithm's running time grows exponentially with the number of dimensions. RRT sidesteps this by drawing random samples, connecting each to the nearest node in a growing tree of trajectories, and discarding any that hit an obstacle.

The algorithm worked well enough to park and unpark the Urban Challenge car. On the forklift, though, it sometimes found a looping trajectory in front of a truck and never got out of the loop, which looked ridiculous in front of the sponsoring army generals. His late advisor kept pushing him to fix it, and the investigation uncovered a fundamental flaw.

The group proved formally that RRT does not converge to optimal solutions. The first trajectories it finds constrain the rest of the search, so more samples never repair a bad early path. Their fix, RRT*, locally corrects paths a little as it goes, which is enough to guarantee asymptotic optimality at almost no extra cost. It became his 2011 doctoral thesis and, in simulation, produced race-car cornering behavior (slow down, hug the apex, speed up) without any hand programming.

Karaman says his group works on autonomous vehicles both individually and as parts of larger systems, such as the roughly 500 robots that bring shelves to pickers in Amazon-style warehouses, fully automated ports, and cooperating delivery drones. Much of the value, he argues, appears only when vehicles work together as a system.

On the vehicle side, the group is motivated by extremely agile machines. He shows a falcon diving at a goose, which looks like a blur on a 20 Hz camera, and describes drones with 200 Hz cameras that carry onboard GPUs and fly with teraflop-class computing. The goal is to perceive, plan and control at very high rates in real time.

An audience question on how controllers are computed leads to the talk's most striking numbers. A six-dimensional state space discretized into 200 points per dimension would need petabytes if you stored one byte for every state. Karaman finds it implausible that a controller truly needs trillions of parameters, so the group starts from a trivial controller, compresses it with singular value decomposition-style techniques, and works in the compressed form.

The result is a lookup table of roughly two megabytes, computed on supercomputers in about five minutes, which can run a kilohertz control loop. He compares it to image and video compression: the more dimensions there are, the more there is to squeeze out, and here the savings reach about ten orders of magnitude.

To show how far coordination can go, Karaman plays a simulation of fully autonomous vehicles crossing an intersection at speed. The cars keep speeding up and slowing down by small amounts to avoid one another, which looks like luck but follows from the math of their acceleration limits. He says you would not want to ride in it, but it shows the fundamental limit, and it could improve warehouse operations where robots now often sit idle.

Asked about robustness in distributed control, he describes a critical density, much like a critical temperature in physics. Below it, paths are easy to find and execution is robust. Above it, the system becomes fragile, and one failure can make everything crash into everything else.

He says existing multi-vehicle systems are far from this regime. Part of the gap is control theory, but a bigger part is that engineers do not yet trust their sensors, so much of the remaining work lies on the sensing side. He then briefly lists other projects, including autonomous tricycles for data collection, a talking warehouse robot, and work with Stanford and Toyota on safer vehicles.

Karaman describes the DARPA Urban Challenge, a race held in November 2007 in which a street-legal robot had to drive 60 miles in under six hours through urban traffic, with U-turns, stop signs and other vehicles. The winner got two million dollars, and 89 teams entered. MIT's team was made up of faculty, postdocs and about eight full-time graduate students, with Draper Laboratory handling system integration and Olin College helping with the vehicle.

The team was talented but inexperienced, and it had plenty of sponsor money. Its strategy was to put everything that fit on a Land Rover LR3, which ended up with five cameras, sixteen radars, twelve planar laser scanners, one 3D laser scanner and a GPS-inertial unit. A 40-core server rack ran the software, powered by an onboard generator and cooled by an air conditioner on the roof.

The Velodyne 64-laser scanner on the roof was the key sensor. It spun at 15 Hz and gave a 3D point cloud, and Karaman guesses the challenge would have been very hard without it. Radars saw about twice as far as lasers but with a narrow field of view, so sixteen were needed to cover 270 degrees. The cameras mainly picked up lane markings.

The software was on the order of 200,000 lines of C, spread over about a hundred processes passing messages. It was organized as a three-tier stack: a navigator like a map app that picks the next waypoint, an RRT motion planner that finds a path to it in the local map, and a controller that steers the vehicle.

Karaman admits the car had barely been tested. The vehicle arrived around April and the race was in November, so the 60-mile race was the farthest it had driven without human intervention. Draper helped with testing, and a simulator that could be swapped for the real sensor data let him run algorithms on two computers around the clock the day before the race.

He then tells the story of an intersection where Cornell's car was stuck in the middle and showed no sign of moving. Officials let MIT's car go ahead, hoping a robot would overtake a stuck robot. MIT's planner kept regenerating trajectories around the partly seen car, but a collision became unavoidable and the car slammed the brakes.

The two teams later wrote a paper together about the incident. Cornell's car apparently believed an obstacle was on top of it, checked each trajectory only for collisions, and did not refresh its map because nothing around it was changing. A person would have stopped to see what was wrong, or at least steered wide, and Karaman notes that these quick inferences, like judging whether a pedestrian is about to step into the road, are very hard for robots.

Both cars finished the race. Six of 89 teams did, and MIT came fourth behind Carnegie Mellon, Stanford and Virginia Tech. Karaman adds that Google's car was effectively a ten-year engineering effort on the laser-scanner-centred design these teams built, while camera-based approaches only began to work once deep learning ran on GPUs.

Asked about the biggest challenge of building from scratch, Karaman says that as a junior student his task was the controllers and parts of RRT, but the hardware and the lack of infrastructure software were major problems. There was no Robot Operating System, so the team built its own messaging layer, LCM (Lightweight Communications and Marshalling). It took the first six or seven months and has since been used widely in industry.

He contrasts the open spirit of those years with today. Back then, competing teams shared findings, as in the Cornell paper, whereas now large investments mean companies expect returns and academics worry about competing with giants. He frames this as part of a longer trend: a century ago top companies built labs that published openly, while today's leaders prefer secretive ones.

He still sees value in competition, and wonders whether DARPA or someone else might run a new challenge, perhaps one using only cameras. DARPA's earlier events reflected defense needs: teams received maps 24 hours in advance and missions just minutes before the run. He thinks a camera-only challenge, with a lot of learning, may be a couple of years from being workable.

Karaman steps back to ask what transportation does to the way we live. He argues that the affordable car drove the suburbs, the central artery in Boston, sprawl in Los Angeles, and congestion and pollution in cities that expanded too fast, like the nine-day, hundred-mile traffic jam in China. Cars themselves are inefficient: a BMW went from about 2,500 to about 4,000 pounds over the decades, so a car weighs roughly 25 times its passengers.

Parking adds to the problem, with about two spots per car in the US, taking up a large part of some cities. Cars have also changed behavior: nobody jaywalks now, because streets belong to cars. Karaman thinks 21st-century technology, including robotics, online services and new business models, offers a chance to redesign this.

He proposes combining autonomy, sharing and electrification, with slower vehicles that need not pass heavy crash tests. In that vision, a trip anywhere in Boston could cost 99 cents with a five-minute wait, 50 cents if shared, and about 30 cents with a single transfer. He thinks cheaper mobility would also create economic activity by changing behavior, for example making a class at Harvard 20 minutes after one at MIT feasible.

Karaman describes the technology landscape as speed versus environmental complexity. Highways (fast but simple) may be conquered within about three years, and slow but complex places like campuses are also promising, but fully autonomous driving everywhere is far off. He says law, insurance, regulation, architecture and business models are as important as the technology.

Karaman closes by mentioning a new company, Optimus, that had just raised a little over five million dollars in seed funding to start autonomous vehicle operations. Its founding team includes Ryan Chin, creator of the MIT City Car, and Albert Wong, who worked with him on the Urban Challenge and later at Google X's Project Wing. He also advises a student team building an autonomous Formula SAE car.

Asked how far away a car is that can navigate Boston using only cameras, with no lidar and no maps, he calls it a guessing game but says he is a big believer in computer vision. Cameras are good sensors but give a lot of data with little information, so computers must fish it out. He would be surprised if it were impossible in ten years, and equally surprised if it happened next year as some claim.

His advice to students working with cameras is to use deep learning, which he calls an excellent technique, but also to try model-based and geometric methods that are also advancing. A solution combining both seems viable to him in perhaps three to five years.

On vehicle communication, he says crazy intersection coordination would require it, but the biggest obstacle to deploying it is cybersecurity. He expects quick wins in lane following and intersections, while some autonomy benefits, such as safety systems and isolated environments, need no communication at all.