Minimum-Time Optimal Control of Many Robots that Move in the Same Direction at Different Speeds
Author:
- 1 April 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 28 (2) , 351-363
Abstract
In this paper, we solve the minimum-time optimal control problem for a group of robots that can move at different speeds but that must all move in the same direction. We are motivated to solve this problem because constraints of this sort are common in micro-scale and nano-scale robotic systems. By application of the minimum principle, we obtain necessary conditions for optimality and use them to guess a candidate control policy. By showing that the corresponding value function is a viscosity solution to the Hamilton-Jacobi-Bellman equation, we verify that our guess is optimal. The complexity of finding this policy for arbitrary initial conditions is only quasilinear in the number of robots, and in fact is dominated by the computation of a planar convex hull. We extend this result to consider obstacle avoidance by explicit parameterization of all possible optimal control policies, and show examples in simulation.Keywords
This publication has 30 references indexed in Scilit:
- Modeling and Experimental Characterization of an Untethered Magnetic Micro-RobotThe International Journal of Robotics Research, 2009
- Control of Many Agents by Moving Their Targets: Maintaining Separation2007
- Broadcast Feedback of Stochastic Cellular Actuators Inspired by Biological Muscle ControlThe International Journal of Robotics Research, 2007
- Control of inhomogeneous quantum ensemblesPhysical Review A, 2006
- An Untethered, Electrostatic, Globally Controllable MEMS Micro-RobotJournal of Microelectromechanical Systems, 2006
- Path coordination for multiple mobile robots: a resolution-complete algorithmIEEE Transactions on Robotics and Automation, 2002
- On Delaying Collision Checking in PRM Planning: Application to Multi-Robot CoordinationThe International Journal of Robotics Research, 2002
- Optimal motion planning for multiple robots having independent goalsIEEE Transactions on Robotics and Automation, 1998
- Optimal paths for a car that goes both forwards and backwardsPacific Journal of Mathematics, 1990
- Sufficient Conditions for Optimality and the Justification of the Dynamic Programming MethodSIAM Journal on Control, 1966