Optimization Techniques for Planning & Estimation in Multi-agent Systems

We are interested in developing computationally efficient algorithms for planning and estimation, with applications to robot teams and wireless sensor networks. This work leverages recent advances in convex optimization. We attempt to extend these by establishing application specific complexity bounds and investigating distributed implementations. Topics of interest include motion planning, multi-robot localization, and target tracking.

Pacman Demo Pacman Demo

Motion Planning

In this work, we investigated techniques for optimal shape changes in robot teams. Our definition of optimality is defined as either minimizing the total distance that the robots must travel or the minimizing the maximum distance that any one robot must travel. Using second-order programming (SOCP) techniques, we derived optimal solutions in both SE(2) and R3. The latter also allows for complete regulation of scale.




In contrast to the more prevalent Bayesian approaches, this work investigated a bounded uncertainty approach to multirobot localization. Range and/or bearing measurements were modeled as linear constraints on the robot positions. The problem of estimating the position of each robot was reduced to bounding the projection of the feasible set of robot positions generated by these constraints. Using an LP formulation, we developed a cutting-plane scheme whereby the projection could be estimated arbitrarily well in polynomial time, and proved a convergence bound. What was perhaps most interesting was that the number of iterations required to bound the individual projections was independent of the number of robots or sensor measurements. Thus, for a given error tolerance, the iteration complexity was O(1) or constant time.