Motion Planning and the Evolution of Autonomous Systems: From DARPA Challenge to Agile Robotics

Sertac Karaman, an MIT professor, details his journey and the evolution of autonomous vehicles, beginning with his involvement in the DARPA Urban Challenge a decade prior. He recounts the development of an autonomous Land Rover LR3, highlighting the shift from academic projects to technologies poised to change the world. Early work also included an autonomous forklift capable of voice and gesture control, predating modern smart assistants like Alexa and Siri, which significantly shaped his PhD research.

The core of Karaman's early work focused on motion planning algorithms. He introduced the Rapidly Exploring Random Tree (RRT) algorithm, explaining its basic principle of sampling the environment to build a tree of collision-free trajectories. However, he critically points out RRT's fundamental flaw: its failure to converge to optimal solutions, often getting stuck in suboptimal loops. This led to his doctoral thesis, the development of RRT* (RRT-star), an algorithm that, with slightly more computational effort, guarantees asymptotic optimality, demonstrated through applications in race car trajectory optimization and complex parking scenarios for forklifts.

His current research group at MIT explores autonomous vehicles at both individual (perception, planning, control) and system levels. On the vehicle level, they push the boundaries of agility, drawing inspiration from natural flyers like falcons to develop drones with ultra-high-rate cameras and GPU-accelerated computing for real-time, complex maneuvers. This involves compressing massive state-space controllers into manageable lookup tables. At the system level, they investigate challenges like optimizing traffic flow at intersections for fully autonomous vehicles and managing large fleets of robots in warehouses, such as Kiva systems.

Karaman also addresses critical challenges in distributed control, such as robustness, introducing the concept of a "critical density" beyond which multi-agent systems become fragile. His group's diverse projects include autonomous tricycles for data collection, warehouse robots, collaborations with Toyota and Stanford for safer vehicles, and integrating electric vehicles in Singapore. He emphasizes the interdisciplinary nature of his team, comprising mathematicians and engineers, and the ongoing need to improve sensor trust and develop robust control mechanisms for the widespread, safe implementation of autonomous systems.

"It is exactly a decade probably today that I shook John Boehner's hand who you've met before I shook John Boehner's hand as a graduate student and joined the dark urban challenge team."

"The one algorithm that I was working on was called rapidly exploring random tree the idea is quite simple... you want to find a path that starts from the initial condition goes to the goal that's the very basic motion planning problem."

"You can prove that any complete algorithm meaning any algum that we towards a solution lamina exists and returns fail or otherwise will scale exponential it's computation time."

"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 the optimal solutions."

"We were able to come up with another album that we called our arty star which just does a little bit more work but guarantees asymptotic optimality meaning it will always converge to optimum solutions."

"The problem is quite interesting both at the vehicle level meaning how are you going to build these autonomous vehicles individually and also interesting other systems that when you think about it most of the autonomous vehicle is most valuable if you put them into a system that they can work."

"You don't really need it would be very surprising if that menu were really to be able to describe it like an information theoretic terms to be able describe it it'd be very surprising if it requires thousands of trillions of parameters."

"You can see 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 could avoid one another."

"Below the critical density things are very simple you're going to be robust you're going to be able to find Pat's and you're going to be able to execute above the critical density things are very hard it's very fairchild like if something fails just kind of the whole system will crash into one another."

"Our strategy turned into if it fits on the vehicle let's put it on the vehicle and we'll figure out a way to use it if we don't use it it's dead weight we'll just kind of carry it."