Optimal Routing and Control of Multiple Agents Moving in a Transportation Network and Subject to an Arrival Schedule and Separation Constraints

Sadovsky, A. V.; Davis, D.; Isaacson, D. R.

We address the problem of navigating a set of moving agents, e.g. automated guided vehicles, through a transportation network so as to bring each agent to its destination at a specified time. Each pair of agents is required to be separated by a minimal distance, generally agent-dependent, at all times. The speed range, initial position, required destination, and required time of arrival at destination for each agent are assumed provided. The movement of each agent is governed by a controlled differential equation (state equation). The problem consists in choosing for each agent a path and a control strategy so as to meet the constraints and reach the destination at the required time. This problem arises in various fields of transportation, including Air Traffic Management and train coordination, and in robotics. The main contribution of the paper is a model that allows to recast this problem as a decoupled collection of problems in classical optimal control and is easily generalized to the case when inertia cannot be neglected. Some qualitative insight into solution behavior is obtained using the Pontryagin Maximum Principle. Sample numerical solutions are computed using a numerical optimal control solver.

Document ID

20130000543

Acquisition Source

Ames Research Center

Document Type

Technical Memorandum (TM)

Authors

Date Acquired

August 27, 2013

Publication Date

July 1, 2012

Subject Category

Report/Patent Number

Funding Number(s)

Distribution Limits

Public

Public Use Permitted.

Available Downloads

Name

Type

20130000543.pdf

STI

No Preview Available

NTRS

NTRS - NASA Technical Reports Server

Available Downloads

Related Records