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

Author Affiliations +

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

ACCESS THE FULL ARTICLE

PERSONAL SIGN IN
Full access may be available with your subscription

Email or Username Forgot your username?

Password Forgot your password?

Show

Remember Email/Username on this computer

Remember Password

No SPIE account? Create an account
or Institutional Sign In via Shibboleth

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

Members: $14.40

Non-members: $18.00 ADD TO CART

Show All Keywords

Keywords/Phrases

Search In:

Publication Years