S*: Geometric Multimodal Trajectory Optimization via Apex Interpolating Spiro Splines

Non-heuristic multimodal trajectory optimization is widely considered an intractable holy grail for real-time robotic systems, with the existing state-of-the-art standing at a heuristic hierarchical approach that stacks upstream search-based or sampling-based behavior planning on top of downstream local numerical trajectory optimization. In this thesis, we present (i) the S* algorithm, a novel geometric trajectory optimization method for autonomous ground vehicles in dynamic environments that uses apex interpolating Spiro splines to optimize orders of magnitude fewer variables than numerical optimization, and (ii) an anytime best-first multimodal variant of S* using a parallel optimistic branch-and-bound on homology classes. We demonstrate a preliminary implementation of this algorithm integrated into MIT Driverless’s autonomous racing stack on a full-size Roborace Devbot 2.0 racecar navigating mixed-reality obstacle courses at up to 100 mph.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Chang, Christopher W.

Advisor dc:contributor.advisor

• Rus, Daniela

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/147490

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/147490