Share Email Print
cover

Proceedings Paper

Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms
Author(s): Kwan S. Kwok; Brian J. Driessen; Cynthia A. Phillips; Craig A. Tovey
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

This work considers the problem of maximum utilization of a set of mobile robots with limited sensor-range capabilities and limited travel distances. The robots are initially in random positions. A set of robots properly guards or covers a region if every point within the region is within the effective sensor range of at least one vehicle. We wish to move the vehicles into surveillance positions so as to guard or cover a region, while minimizing the maximum distance traveled by any vehicle. This problem can be formulated as an assignment problem, in which we must optimally decide which robot to assign to which slot of a desired matrix of grid points. The cost function is the maximum distance traveled by any robot. Assignment problems can be solved very efficiently. Solution times for one hundred robots took only seconds on a silicon graphics crimson workstation. The initial positions of all the robots can be sampled by a central base station and their newly assigned positions communicated back to the robots. Alternatively, the robots can establish their own coordinate system with the origin fixed at one of the robots and orientation determined by the compass bearing of another robot relative to this robot. This paper presents example solutions to the multiple-target-multiple-agent scenario using a matching algorithm. Two separate cases with one hundred agents in each were analyzed using this method. We have found these mobile robot problems to be a very interesting application of network optimization methods, and we expect this to be a fruitful area for future research.

Paper Details

Date Published: 22 September 1997
PDF: 12 pages
Proc. SPIE 3209, Sensor Fusion and Decentralized Control in Autonomous Robotic Systems, (22 September 1997); doi: 10.1117/12.287630
Show Author Affiliations
Kwan S. Kwok, Sandia National Labs. (United States)
Brian J. Driessen, Sandia National Labs. (United States)
Cynthia A. Phillips, Sandia National Labs. (United States)
Craig A. Tovey, Georgia Institute of Technology (United States)


Published in SPIE Proceedings Vol. 3209:
Sensor Fusion and Decentralized Control in Autonomous Robotic Systems
Paul S. Schenker; Gerard T. McKee, Editor(s)

© SPIE. Terms of Use
Back to Top