Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms

Kwan S. Kwok; Brian J. Driessen; Cynthia A. Phillips; Craig A. Tovey

doi:10.1117/12.287630

22 September 1997 Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms

Kwan S. Kwok, Brian J. Driessen, Cynthia A. Phillips, Craig A. Tovey

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.

Citation Download Citation

Kwan S. Kwok, Brian J. Driessen, Cynthia A. Phillips, and 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); https://doi.org/10.1117/12.287630

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available