COLLOQUIUM Department of Computer Science and Engineering University of South Carolina Lantao Liu Department of Computer Science and Engineering Texas A&M University Date: April 11, 2013 Time: 1400-1500 (2:00pm-3:00pm) Place: Swearingen 1A03 (Faculty Lounge) Abstract Like humans, multiple robots need to collaborate with each other to accomplish certain missions efficiently. Task allocation (or assignment) is an important component for building multi-robot systems that behave as a coordinated whole. This talk will cover two settings in which coordination methods using task allocation techniques are effective; the two settings bring together ideas from different fields: distributed AI, operations research, graph theory, high performance computation, and economics. Specifically, I will introduce two decentralized task assignment methods: (1) a multi-level assignment decentralization framework based on matrix partitioning in order to cluster the strongly related robot-tasks pairs, and (2) a task-swap based assignment algorithm with many unique features that are particularly suitable for distributed multi-robot task allocation. Furthermore, I am also going to discuss how the classic assignment algorithms can still be extended to solve new problems in the multi-robot domain, e.g., how the combinatorial assignment algorithm itself can be extended to tackle the task allocation involving uncertainty; and how the matching bigraph data structure of the assignment algorithm can be manipulated to solve the robotics routing and formation control problems. Lantao Liu is a Ph.D. candidate (with dissertation successfully defended) in the Department of Computer Science and Engineering at Texas A&M University. Liu works on developing coordination methods for multiple robots. His dissertation was on task allocation problems. Liu also works on estimating and analyzing the properties of swarm systems, motion planning for robotics, and protein folding in computational biology. Recently, Liu has been awarded the prestigious Texas A&M University Dissertation Fellowship and the Chinese Government Scholarship for outstanding students abroad, which is based on nominations by Chinese embassies worldwide. Liu graduated with highest honors (academic silver medalist) from the Department of Automatic Control at Beijing Institute of Technology in 2007.