Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T08:33:15.916Z Has data issue: false hasContentIssue false
  • English
  • Français

Motion planning for multiple robots with multi-mode operations via disjunctive graphs*

Published online by Cambridge University Press:  09 March 2009

Chi-Fang Lin  and
Wen-Hsiang Tsai
Get access Rights & Permissions [Opens in a new window]

Summary

A new approach to motion planning for multiple robots with multi-mode operations is proposed in this paper. Although sharing a common workspace, the robots are assumed to perform periodical tasks independently. The goal is to schedule the motion trajectories of the robots so as to avoid collisions among them. Rather than assigning the robots with different priorities and planning safe motion for only one robot at a time, as is done in most previous studies, an efficient method is developed that can simultaneously generate collision-free motions for the robots with or without priority assignment. Being regarded as a type of job-shop scheduling, the problem is reduced to that of finding a minimaximal path in a disjunctive graph and solved by an extension of the Balas algorithm. The superiority of this approach is demonstrated with various robot operation requirements, including “non-priority”, “with-priority”, and “multicycle” operation modes. Some techniques for speeding up the scheduling process are also presented. The planning results can be described by Gantt charts and executed by a simple “stop-and-go” control scheme. Simulation results on different robot operation modes are also presented to show the feasibility of the proposed approach.

Keywords

Robot OperationMotion PlanningSchedule MapDisjunctive Graph
Type
Article
Information
Robotica , Volume 9 , Issue 4 , December 1991 , pp. 393 - 408
Copyright
Copyright © Cambridge University Press 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Lozano-Pérez, T., “Spatial planning: a configuration space approach” IEEE Trans. on Computers C-32, 108–120 (02, 1983).CrossRefGoogle Scholar
2.Brooks, R.A. and Lozano-Pérez, T., “A subdivision algorithm in configuration space for findpath with rotation” IEEE Trans. on Syst., Man, and Cybern. SMC-15, No. 2, 224–233 (1985).Google Scholar
3.Brooks, R.A., “Solving the find-path problem by good representation of free space” IEEE Trans. on Syst., Man, Cybern. SMC-13, No. 3, 190–197 (1983).Google Scholar
4.Lozano-Pérez, T., “A simple motion-planning algorithm for general robot manipulators” IEEE J. Robotics and Automation RA-3, 224–238 (06, 1987).CrossRefGoogle Scholar
5.Ruff, R. and Ahuja, N., “Path planning in a three dimensional environment” Proc. Int. Conf. on Pattern Recognition,Montreal, Canada188–191 (1984).Google Scholar
6.Lee, B.H. and Lee, C.S.G.., “Collision-free motion planning of two robots” IEEE Trans. on Syst., Man, Cybern. SMC-17, No. 1, 21–32 (1987).Google Scholar
7.Liu, Y.H. et al. , “A practial algorithm for planning collision-free coordinated motion of multiple mobile robots” In: Proc. IEEE Int. Conf. on Robotics and Automation,Washington, D.C. (IEEE Computer Society Press, New York, 1989) pp. 1427–1432.Google Scholar
8.Fujimura, K. and Samet, H., “A hierarchical strategy for path planning among moving obstacles, IEEE Trans. on Robotics and Automation 5, 61–69 (02, 1989).CrossRefGoogle Scholar
9.Kant, K. and Zucker, S.W., “Toward efficient trajectory planning: the path-velocity decomposition” Int. J. Robotics Research 5, 72–89 (Fall, 1986).CrossRefGoogle Scholar
10.Erdmann, M. and Lozano-Pérez, T., “On multiple moving objects” Algorithmica 2, No. 4, 477–521 (1987).CrossRefGoogle Scholar
11.Lin, C.F. and Tsai, W.H., “Trajectory modeling, collision detection, and motion planning for robot manipulators” NSC Technical Report No. NSC78–0404-E009–04, National Chiao Tung University, Hsinchu, Taiwan 30050, Republic of China (submitted for publication).Google Scholar
12.Balas, E., “Machine sequencing via disjunctive graphs: an implicit enumeration algorithm” Operations Research 17, No. 6, 941–957 (1969).CrossRefGoogle Scholar
13.Ashour, S., Moore, T.E. and Chiu, K.Y., “An implicit enumeration algorithm for the nonpreemptive shop scheduling problem” AIIE Transactions 6, No. 1, 62–72 (1974).Google Scholar
14.Florian, M., Trepant, P. and McMahon, G., “An implicit enumeration algorithm for the machine sequencing problem” Management Science 17, B782–B792 (08, 1971).CrossRefGoogle Scholar
15.Greenberg, H.H., “A branch-bound solution to the general scheduling problem” Operations Research 16, No. 2, 353–361 (1968).CrossRefGoogle Scholar
16.Hardgrave, W.W. and Nemhauser, G.L., “A geometric model and a graphical algorithm for a scheduling problem” Operations Research 11, No. 6, 889–900 (1963).CrossRefGoogle Scholar
17.Lageweg, B.J., Lenstra, J.K. and Kan, A.H.G.R., “Job-shop scheduling by implicit enumeration” Management Science 24, 441–450 (12, 1977).CrossRefGoogle Scholar
18.Lenstra, J.K. et al. , “Complexity of machine scheduling problems” Ann. Discrete Math. 7, 343–362 (1977).CrossRefGoogle Scholar
19.Garey, M.R., Johnson, D.S. and Sethi, R., “The complexity of flowshop and jobshop scheduling” Mathematics of Operations Research 1, No. 2, 117–129 (1976).CrossRefGoogle Scholar
20.Boyse, J.W., “Interference detection among solids and surfaces” Comm. of the ACM 22, 3–9 (01, 1979).CrossRefGoogle Scholar