Share Email Print

Proceedings Paper

Scheduling And Path Planning Of Multiple Robots In A Factory
Author(s): Alex C.C. Meng; Yong F. Choong; Michael Sullivan
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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].

Paper Details

Date Published: 21 March 1989
PDF: 11 pages
Proc. SPIE 1095, Applications of Artificial Intelligence VII, (21 March 1989); doi: 10.1117/12.969289
Show Author Affiliations
Alex C.C. Meng, Texas Instruments, Inc. (United States)
Yong F. Choong, Texas Instruments, Inc. (United States)
Michael Sullivan, Texas Instruments, Inc. (United States)

Published in SPIE Proceedings Vol. 1095:
Applications of Artificial Intelligence VII
Mohan M. Trivedi, Editor(s)

© SPIE. Terms of Use
Back to Top