21 March 1989 Scheduling And Path Planning Of Multiple Robots In A Factory
Author Affiliations +
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].
© (1989) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
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

Back to Top