Loading Events

« All Events

  • This event has passed.

GRASP Special Seminar – Brandon Basso, University of California, Berkeley, “Learned Vehicle Routing”

April 10, 2012 @ 10:00 am - 11:00 am

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

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.


- Learn More

Brandon Basso is a PhD candidate in control
theory at The University of California, Berkeley in the mechanical engineering department.
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.

Brandon has been a member of the Centre for Collaborative Control
of Unmanned Vehicles (C3UV) at UC Berkeley under Karl Hedrick. In
2010, he orchestrated a large-scale field robotics demonstration involving
several autonomous aircraft collaborating to track a pedestrian while
concurrently negotiating in real time to perform other tasks. This achievement
was featured in the cover article of ASME Mechanical Engineering Magazine,
April 2011. In addition to closed loop vision-based pedestrian tracking,
the demonstration validated the underlying system architecture that Brandon
designed, implemented, and deployed on the aircraft. Since then, his
architecture operated a Boeing unmanned aircraft system in a similar scenario,
demonstrating the portability of the software and validating the philosophy
of component-based software design for robotics.


April 10, 2012
10:00 am - 11:00 am
Event Category: