Pushing Multi-agent Systems to Extremes: From Coordinate Free Rendezvous to Optimal Formation Planning


Event Location: 


Event Date/Time: 

Monday, August 27, 2012 - 4:45pm

Research Area: 

"Pushing Multi-agent Systems to Extremes: From Coordinate Free Rendezvous to Optimal Formation Planning"

Speaker: Jingjin Yu, University of Illinois at Urbana-Champaign
Date: Thursday, August 30 2012
Time: 1:30PM to 2:30PM
Location: D507
Host: Russ Tedrake, MIT
Contact: Mieke Moran, 617-253-5817, mieke@csail.mit.edu

Relevant URL: http://jingjinyu.com/ 

In the past decade or so, multi-agent (multi-robot) systems have received considerable attention in control theory and robotics (for representative works, see Ando et al. 1999 and Jadbabaie et al. 2003). Due to their inherent complexity, results on these systems usually depend on full state estimations to prove convergence, often without optimality assurance. In this talk, we push multi-agent systems to extremes on both fronts. In taking sensing requirements to the limit, we show that multiple Dubins car vehicles can achieve distributed rendezvous in a coordinate free fashion, with a three-state bearing only sensing model and a simple quantized control law. The key to establishing convergence lies with applying Lagrange multipliers to a novel non-quadratic Lyapunov certificate. Moving to the optimality front, we provide efficient (centralized) network flow based algorithms that compute time/distance optimal paths for indistinguishable agents on graphs. For example, our algorithm can plan distance optimal paths, with a tight convergence time guarantee, for 500 agents on a 10000 vertex graph to achieve arbitrary final formation in a few seconds. 

Jingjin Yu received a B.S. degree in materials engineering from USTC, Hefei, China (1998), an M.S. degree in chemistry from the University of Chicago (2000), an M.S. degree in mathematics from the University of Illinois at Chicago (2001), and an M.S. degree in computer science from the University of Illinois at Urbana Champaign (2010). He is currently a Ph.D. candidate with the Department of Electrical and Computer Engineering at the University of Illinois at Urbana Champaign. His research interests include robotics and control theory.