Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-18T19:31:07.523Z Has data issue: false hasContentIssue false
  • English
  • Français

Mechanization of spatial reasoning for automatic pipe layout design

Published online by Cambridge University Press:  27 February 2009

David Zhu  and
Jean-Claude Latombe
David Zhu
Affiliation:
Robotics Laboratory, Department of Computer Science, Stanford University, Stanford, CA 94305, U.S.A.
Jean-Claude Latombe
Affiliation:
Robotics Laboratory, Department of Computer Science, Stanford University, Stanford, CA 94305, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

Artificial Intelligence has been very active in developing high-level symbolic reasoning paradigms that have resulted in practical expert systems. However, with a few exceptions, it has paid little attention to the automation of spatial reasoning. On the other hand, spatial reasoning has attracted the interest of several researchers in Robotics. One of the important problems that have been investigated is motion planning, and very significant results have been obtained. This paper describes an implemented system for designing pipe layouts automatically using motion planning techniques. It introduces a new approach to pipe layout design automation in which pipe routes are treated as trajectories left behind by rigid objects (‘robots’). We have implemented this approach in a basic Pipe Router that is described in detail in this paper. We have extended this router in order to make it capable of treating a variety of other constraints which are typical of practical pipe layout design problems. These constraints relate to the process carried out in the pipes, to the design of their mechanical support, and to the constructability and the ease of operation and maintenance of the designed pipe systems.

Type
Research Article
Information
AI EDAM , Volume 5 , Issue 1 , February 1991 , pp. 1 - 20
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

Barraquand, J. and Latombe, J. C. 1989 a. Robot Motion Planning: A Distributed Representation Approach, Report No. STAN-CS-89–1257, Department of Computer Science, Stanford University.CrossRefGoogle Scholar
Barraquand, J. and Latombe, J. C. 1989 b. On non-holonomic mobile robots and optimal maneuvering. Revue d’Intelligence Artificielle, 3(2), 77–103.Google Scholar
Bechtel 1986. Expanding CAD applications on petroleum projects. Bechtel CAE Bulletin.Google Scholar
Brooks, R. A. and Lozano-Pérez, T. 1982. A Subdivision Algorithm in Configuration Space for Findpath with Rotation, AI Memo 684, Artificial Intelligence Laboratory, MIT, Cambridge, MA.Google Scholar
Chambon, R., Tollenaere, M., Chevalier, P. M. and Descotte, Y. 1987. An expert system for objects placing in three-dimensional space. KBES in Engineering: Planning and Design, 447–459.Google Scholar
Donald, B. R. 1983. The mover’s problem in automated structural design. Proceedings of the Harvard Computer Graphics Conference, Cambridge, MA.Google Scholar
Donald, B. R. and Pai, D. K. 1989. On the Motion of Compliantly-Connected Rigid Bodies in Contact, Part II: A system for Analyzing Design for Assembly, TR 89–1048, Department of Computer Science, Cornell University, Ithaca, NY.Google Scholar
Erdmann, M. and Lozano-Pérez, T. 1986. On Multiple Moving Objects, AI Memo No 883, Artificial Intelligence Laboratory, MIT, Cambridge, MA.CrossRefGoogle Scholar
Faverjon, B. and Tournassoud, P. 1989. A practical approach to motion planning for manipulators with many degrees of freedom. Preprints of the Fifth International Symposium of Robotics Research, Tokyo, 65–73.Google Scholar
Fortune, S. and Wilfong, G. 1988. Planning constrained motion. Proceedings of the Fourth ACM Symposium on Computation Geometry, 445–459.Google Scholar
Gunn, D. J. and Al-Asadi, H. D. 1987. Computer-aided layout of chemical plant: a computational method and case study. Computer Aided Design 19(3), 131–140.CrossRefGoogle Scholar
Hasan, H. and Liu, C. L. 1986. A force-directed global router. Proceedings of the Stanford Conference on VLSI Design, 135–150.Google Scholar
Jacobs, P. and Canny, J. 1989. Planning smooth paths for mobile robots. Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, AZ, 2–7.Google Scholar
Khatib, O. 1986. Real-time obstacle avoidance for manipulators and mobile robots. International Journal of Robotics Research 5, 90–98.CrossRefGoogle Scholar
Kobayashi, Y., Wada, Y. and Kiguchi, T. 1986. Knowledge representation and utilization for optimal route search. IEEE Transactions on Systems, Man, and Cybernetics, 454–462.Google Scholar
Latombe, J. C, 1976. Artificial intelligence in computer-aided design: the tropic system. IFIP Working Conference, Austin, TX (Allan, J. J., ed.), pp. 61–120. Amsterdam: North Holland.Google Scholar
Latombe, J. C. 1979. Failure processing in a system for designing complex assemblies. Sixth International Joint Conference on Artificial Intelligence (IJCAI), Tokyo, Japan.Google Scholar
Latombe, J. C. 1988. Spatial reasoning: from robotics to engineering. Second Toyota Conference on Organization of Engineering Knowledge for Product Modeling in Computer Integrated Manufacturing, Nagoya. (Sata, T., ed.), pp. 83–105Amsterdam: Elsevier.Google Scholar
Latombe, J. C. 1991. Robot Motion Planning. Boston, MA: Kluwer.CrossRefGoogle Scholar
Laumond, J. P. 1987. Finding collision-free smooth trajectories for a non-holonomic mobile robot. Proceedings of the 10th International Joint Conference on Artificial Intelligence, Milan, Italy, pp. 1120–1123.Google Scholar
Lozano-Pérez, T. 1983. Spatial planning: a configuration space approach. IEEE Transactions on Computers, C-32(2), 108–120.CrossRefGoogle Scholar
Mitsuta, T., Kobayashi, Y., Wada, Y., Kiguchi, T. and Yoshinaga, T. 1986. A knowledge-based approach to routing problems in industrial plant design. 6th International Workshop on Expert Systems and Their Applications, Avignon, France, pp. 237–255.Google Scholar
Natarajan, B. K. 1989. Some paradigms for the automated design of parts feeders. International Journal of Robotics Research 8(6), 98–109.CrossRefGoogle Scholar
Nilsson, N. J. 1980. Principles of Artificial Intelligence. Palo Alto, CA: Morgan Kaufmann.Google Scholar
Ó’Dúnlaing, C. and Yap, C. K. 1982. A retraction method for planning the motion of a disc. Journal of Algorithms 6, 104–111.CrossRefGoogle Scholar
Preparata, F. P. and Shamos, M. I. 1985. Computational Geometry: An Introduction. New York: Springer.CrossRefGoogle Scholar
Reif, J. H. 1979. Complexity of the mover’s problem and generalizations. Proceedings of the 20th IEEE Symposium of Foundations of Computer Science, pp. 144–154.Google Scholar
Sechen, C. 1988. VLSI Placement and Global Routing Using Simulated Annealing. Boston, MA: Kluwer.CrossRefGoogle Scholar
Schwartz, J. T. and Sharir, M. 1983. On the piano movers’problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Communications on Pure and Applied Mathematics 36, 345–398.CrossRefGoogle Scholar
Schwartz, J. T., Sharir, M. and Hopcroft, J. 1987. Planning, Geometry, and Complexity of Robot Motion. Norwood, NJ: Ablex.Google Scholar
Sheridan, H. C. 1976. An overview of a CASDAC subsystemcomputer-aided piping design and construction (CAPDAC). Naval Engineers Journal 87–98.CrossRefGoogle Scholar
Sifrony, S. and Sharir, M. 1987. A new efficient motion planning algorithm for a rod in two-dimensional polygonal space. Algorithmica 1, 367–402.CrossRefGoogle Scholar
Stallman, R. M. and Sussman, G. J. 1977. Forward reasoning and dependency-directed backtracking in a system for computedaided circuit analysis. Artificial Intelligence 9(2), 135–196.CrossRefGoogle Scholar
Wangdahl, G. E. et al. 1974. Minimum-trajectory pipe routing. Journal of Ship Research 18(1), 46–49.CrossRefGoogle Scholar
Wilson, R. H. and Rit, J. F. 1990. Maintaining geometric dependencies in an assembly planner. Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, OH, 890–895.Google Scholar
Zhu, D. J. and Latombe, J. C. 1991. New heuristic algorithms for efficient hierarchical path planning. IEEE Transactions of Robotics and Automation 7, 9–20.CrossRefGoogle Scholar