22 September 1997 Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms
Author Affiliations +
Proceedings Volume 3209, Sensor Fusion and Decentralized Control in Autonomous Robotic Systems; (1997) https://doi.org/10.1117/12.287630
Event: Intelligent Systems and Advanced Manufacturing, 1997, Pittsburgh, PA, United States
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.
© (1997) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Kwan S. Kwok, Kwan S. Kwok, Brian J. Driessen, Brian J. Driessen, Cynthia A. Phillips, Cynthia A. Phillips, Craig A. Tovey, Craig A. Tovey, } "Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms", Proc. SPIE 3209, Sensor Fusion and Decentralized Control in Autonomous Robotic Systems, (22 September 1997); doi: 10.1117/12.287630; https://doi.org/10.1117/12.287630
PROCEEDINGS
12 PAGES


SHARE
Back to Top