Minimum-time optimal control of many robots that move in the same direction at different speeds

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number6087289
Pages (from-to)351-363
Number of pages13
JournalIEEE Transactions on Robotics
Issue number2
StatePublished - Apr 2012


  • Motion planning
  • multi-robot systems
  • optimal control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Minimum-time optimal control of many robots that move in the same direction at different speeds'. Together they form a unique fingerprint.

Cite this