Scheduling And Path Planning Of Multiple Robots In A Factory

Alex C.C. Meng; Yong F. Choong; Michael Sullivan

doi:10.1117/12.969289

21 March 1989 Scheduling And Path Planning Of Multiple Robots In A Factory

Alex C.C. Meng, Yong F. Choong, Michael Sullivan

Proceedings Volume 1095, Applications of Artificial Intelligence VII; (1989) https://doi.org/10.1117/12.969289
Event: SPIE 1989 Technical Symposium on Aerospace Sensing, 1989, Orlando, FL, United States

Abstract

This paper describes the work in progress for scheduling and planning paths for map-guided robots (AGVs) maneuvering in a dynamic factory floor environment. A schedule of a group of robots consists of a set of paths to be traversed and the start, stop and wait time at each point of a single robot's path segment. The optimal schedule will minimize the finish time of all the robots's tasks. We will show that the optimal routing problem for multiple robots is computationally intractable (NP-Complete). Our methodology is to generate reasonably good schedules in time by combining techniques from two different disciplines. We use a time map management system from artificial intelligence (AI) research to generate an initial schedule quickly, then we pass the initial schedule to an iterative refinement loop (or local search) to gradually improve it locally using an optimization process from operations research (OR). We will briefly recount the basic principles for map-guided autonomous navigation, which has been published in [Meng88b].

Citation Download Citation

Alex C.C. Meng, Yong F. Choong, and Michael Sullivan "Scheduling And Path Planning Of Multiple Robots In A Factory", Proc. SPIE 1095, Applications of Artificial Intelligence VII, (21 March 1989); https://doi.org/10.1117/12.969289

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