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.
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.
- Google Scholar “Convex Optimization Strategies for Coordinating Large-scale Robot Formations”, IEEE Transactions on Robotics (T-RO), vol 23, num 6, pp 1252-1259, December 2007. Full text –
- Google Scholar “A Graph Theoretic Approach to Optimal Target Tracking for Mobile Robot Teams”, In the Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), San Diego, CA, October 2007. Full text –
- Google Scholar “Efficient Motion Planning Strategies for Large-scale Sensor Networks”, Workshop on the Algorithmic Foundations of Robotics (WAFR) ’06, New York, NY, July 2006. Full text –
- Google Scholar , “Optimal Shape Changes for Robot Teams”, Lehigh University Technical Report LU-CSE-05-029. Full text –
- Google Scholar and R. Fierro, “Optimal Positioning Strategies for Shape Changes in Robot Teams”, in the Proceedings of the IEEE International Conference on Robotics and Automation, pp. 754-759, Barcelona, April 2005. Full text –
- Optimal Target Tracking Using SDP w/ Weighted Graph Laplacians (four agents tracking three targets) (.mp4)
- Evolution of Optimal Visibility (green) and Network (blue) Graphs in a Simple Target Tracking Scenario (.mp4)
- Distributed Shape Change on Sony Aibos (.wmv)
- Pacman Shape Change in SE(2) (.mpg)
- Optimal Deployment of a Mobile Ad-hoc Network (MANET) (.mpg)
- Pyramid Shape Change in R3 (.mpg)
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.
Full text – Google Scholar
, “A Bounded Approach to Cooperative Localization Using Relative Bearing Constraints”, In the Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), San Diego, CA, October 2007.
- Google Scholar , “A Bounded Uncertainty Approach to Multi-robot Localization”, In Proceedings of IROS 2003, pp. 1258-1265, Las Vegas, USA, Oct 2003. Full text –
- John Spletzer
- Jason Derenick