Dynamic programming solution for a class of pursuit evasion problems: the herding problem

Author

Kachroo, Pushkin ; Shedied, Samy A. ; Bay, John S. ; Vanlandingham, Hugh

Author_Institution

Bradley Dept. of Electr. Eng., Virginia Polytech. Inst. & State Univ., Blacksburg, VA, USA

Volume

31

Issue

1

fYear

2001

fDate

2/1/2001 12:00:00 AM

Firstpage

35

Lastpage

41

Abstract

A herding dog and sheep problem is studied where the agent “dog” is considered the control action for moving the agent “sheep” to a fixed location using the dynamics of their interaction. The problem is solved for the deterministic case using dynamic programming. Proofs are provided for the correctness of the algorithms. The algorithm is analyzed for its complexity. A software package developed for experimentation is described

Keywords

computational complexity; dynamic programming; mathematics computing; program verification; algorithm correctness; complexity; control action; deterministic case; dynamic programming; dynamic programming solution; fixed location; herding dog; herding problem; interaction dynamics; pursuit evasion problems; sheep problem; software package; Algorithm design and analysis; Costs; Difference equations; Dynamic programming; Game theory; Helium; Indium tin oxide; Information technology; Software packages; Stochastic processes;

fLanguage

English

Journal_Title

Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on

Publisher

ieee

ISSN

1094-6977

Type

jour

DOI

10.1109/5326.923266

Filename

923266