Optimization Techniques for Planning & Estimation in Multi-agent Systems

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.

pac1

pac2

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.

Papers

  • J. Derenick and J. Spletzer, “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
  • J. Derenick, J. Spletzer and M. Ani Hsieh, “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
  • J. Derenick, C. Mansley and J. Spletzer, “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
  • J. Derenick and J. Spletzer, “Optimal Shape Changes for Robot Teams”, Lehigh University Technical Report LU-CSE-05-029. Full text – Google Scholar
  • J. Spletzer 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 – Google Scholar

Media //vader

Localization

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.

Papers

  • C.J. Taylor and J. Spletzer, “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.
    Full text – Google Scholar
  • J. Spletzer and C.J. Taylor, “A Bounded Uncertainty Approach to Multi-robot Localization”, In Proceedings of IROS 2003, pp. 1258-1265, Las Vegas, USA, Oct 2003. Full text – Google Scholar

People