CSAIL Event Calendar

Learned Vehicle Routing

Abstract: Autonomous decision making is a broad field that encapsulates many topics germane to autonomous systems. The vehicle routing problem (VRP) is a particularly well-studied decision problem in which the goal is to find an optimal allocation of agents to tasks while respecting spatial, temporal, and capacity constraints. Air traffic control, postal service package delivery, and many other similar applications can generally be categorized as multi-agent vehicle routing. Traditional solution approaches have a difficulty in coping with such broad problems, characterized by vast state spaces, evolving constraints, unstructured environments, and ambiguous state transition dynamics.

Departing from traditional optimization and search-based approaches, this work seeks to pose vehicle-routing-based problems in a machine learning context. A representation scheme is presented that scales independently of the physical problem size. The abstracted cost-based state captures an agent’s ability to perform a certain task, transferring complexity from constraints into the state itself. In order to capture temporal constraints such as deadlines without increasing complexity, a semi-Markov model is proposed and analyzed relative to a traditional Markov model. Well-known iterative learning algorithms based on dynamic programming readily solve for optimal policies and can be compared to known VRP solutions. Results borne out in simulation demonstrate the benefits of modeling high-level decision problems such as VRPs in a learning framework.

Bio: Brandon Basso is a PhD candidate in control theory at the University of California, Berkeley in the mechanical engineering department and a member of the Centre for Collaborative Control of Unmanned Vehicles (C3UV) at UC Berkeley under Karl Hedrick. He earned a B.S. degree in mechanical engineering from Columbia University in 2005, and a M.S. from UC Berkeley in 2009. Brandon’s current research focuses on autonomous decision making among teams of robotic aircraft. Prior to attending Berkeley, Brandon worked at Honeybee Robotics in New York City and was member of the Mars Exploration Rover engineering team, contributing to the daily operation of Rock Abrasion Tools aboard the Spirit and Opportunity rovers.

See other events happening in July 2012