Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-19T02:13:39.476Z Has data issue: false hasContentIssue false
  • English
  • Français

Solving the motion planning problem by using neural networks

Published online by Cambridge University Press:  09 March 2009

R.H.T. Chan ,
P.K.S. Tam  and
D.N.K. Leung
Get access Rights & Permissions [Opens in a new window]

Summary

This paper presents a new neural networks-based method to solve the motion planning problem, i.e. to construct a collision-free path for a moving object among fixed obstacles. Our ‘navigator’ basically consists of two neural networks: The first one is a modified feed-forward neural network, which is used to determine the configuration space; the moving object is modelled as a configuration point in the configuration space. The second neural network is a modified bidirectional associative memory, which is used to find a path for the configuration point through the configuration space while avoiding the configuration obstacles. The basic processing unit of the neural networks may be constructed using logic gates, including AND gates, OR gates, NOT gate and flip flops. Examples of efficient solutions to difficult motion planning problems using our proposed techniques are presented.

Keywords

Motion planningNeural networkConfiguration spaceDistance transform.
Type
Article
Information
Robotica , Volume 12 , Issue 4 , July 1994 , pp. 323 - 333
Copyright
Copyright © Cambridge University Press 1994

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-Perez, T. and Wesley, M.A., “An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles” Communication of ACM 22, No. 10, 165–175 (10. 1979).Google Scholar
2.Lozano-Perez, T., “Spatial Planning: A configuration Space Approach” IEEE Transactions on Computers C-32, No. 2, 108–120 (1983).Google Scholar
3.Brooks, R.A. and Lozano-Perez, T., “A Subdivision Algorithm in Configuration Space for FindPath with Rotation” Proc. 1JCAI (1983) pp. 799–806.Google Scholar
4.Brooks, R.A., “Solving the Find-Path Problem by Good Representation of Free Space” IEEE Trans. on System, Man and Cybernetics SMC-13, No. 3, 190–197 (03/04, 1983).CrossRefGoogle Scholar
5.Schwartz, J.T. and Sharir, M., “On the Piano Movers' Problem: I. The Case of a Two-Dimensional Polygonal t Body Moving Amidst Polygonal Barriers” Communicadons on Pure and Applied Mathematics 36, 345–398 (1983).CrossRefGoogle Scholar
6.Schwartz, J.T. and Sharir, M., “On the Piano Movers' Problem: II General Techniques for Computing Toplogical Properties of Real Algebraic Manifolds” Advances in Applied Mathematics 4, 298–351 (1983).Google Scholar
7.Reif, J.H., “Complexity of o the Generalized Mover's Problem”, Proc. of the IEEE Symposium on Foundations of Computer Science (1979) pp. 421–427.Google Scholar
8.Zhu, D. and Latcombe, J.C., “New Heuristic Algorithms for Efficient Hierarchical Path Planning” IEEE Transac t tions on Robotics and Automation 7, No. 1, 9–20 (02, 1991).CrossRefGoogle Scholar
9.Tsingpin, B. and Xueyin, L., “Safe Path Network: A New Approach to Path-Planning” Proc. of IEEE Conf. on Robotics and Automation (1988) pp. 917–921.Google Scholar
10.Zhang, B., Zhang, L. and Zhang, J., “An Algorithm for FindPath With Rotation” Proc. of IEEE Conf. on; Robotics and Automation (1988) pp. 795–798.Google Scholar
11.Ozaki, H., Shimadzu, T. and Mohri, A., “Collision-free Path Generation for a Mobile Robot by an Artificial Transformation of Obstacle Space” Robotica 7, Part 2, 139–142 (1989).CrossRefGoogle Scholar
12.Ahmed, H. and Biswas, S., “Path Planning: A New Look at Free Space Characterization” Proc. of Inter. Conf. on Automation, Robotics and Computer Vision (1990) pp. 539–543.Google Scholar
13.Arimoto, S., Noborio, H., Fukuda, S. and Noda, A., “A Feasible Approach to Automatic Planning of Collision-Free Robot Motions ” The Fourth International Symposium on Robotics Research (1988) pp. 479–488.Google Scholar
14.Takahashi, O. and Schilling, R.J., “Motion Planning in a Plane Using Generalized Voronoi Diagrams” IEEE Transactions on Robotics and Automation 5, No. 2, 143–150 (04, 1989).CrossRefGoogle Scholar
15.Jarvis, R.A., “Growing Polyhedral Obstacles for Planning Collision-Free Paths”, The Australian Computer J 15, No. 3 103–110 (08 1983).Google Scholar
16.Oommen, B.J., Iyengar, S.S., Rao, S.V.N. and Kashyap, R.L., “Robot Navigation in Unknown Terrains of Convex Polygonal Obstacles using Learned Visibility Graphs”, Proceedings AAAI-86 (08, 1986) pp. 1101–1106.Google Scholar
17.Canny, J. and Donald, B., “Simplified Voronoi Diagram” Discrete and Computational Geometry 3, No. 3, 219–236 (1988).CrossRefGoogle Scholar
18.Rueb, K.D., Wong, A.K.C., “structuring Free Space as a Hypergraph for Roving Robot Path Planning and Navigation” IEEE Trans. on Pattern Analysis and Machine Intelligence 9(2), 263–273 (03, 1987).Google Scholar
19.Laumond, K. P., “Model Structu?ng and Concept Recognition: Two Aspects of Learning for a Mobile Robot”, Proceedings IJCAI-83 (08, 1983) pp. 835–841.Google Scholar
20.Steele, J.P.H. and Stan, G.P., “Path Planning and Heuristic for Mobile Robots in Real World Environments” Proc. of Inter. Conf. on Systems, Man & Cybernetics (10, 1987) pp. 365–369.Google Scholar
21.Thorpe, C.E., “Path Relaxation' Path Planning for a Mobile Robot” Proc. Nat. Cong. Artificial Intell. (1984) pp. 318–321.Google Scholar
22.Chan, R.H.T., Tam, P.K.S. and Leung, D.N.K., “Robot Navigation in Unknown Terrains via Multi-resolution Grid Maps” Proc. of the IEEE IECON'91 Inter. Conf. on Industrial Electronics, Control and Instrumentation 2 (11, 1991) pp. 1138–1143.CrossRefGoogle Scholar
23.Lippman, R.P., “An Introduction to Computing with Neural Nets” IEEE ASSP Magazine 4–22 (04, 1987).CrossRefGoogle Scholar
24.Jorgensen, C.C., “Neural Network Representation of Sensor Graphs in Autonomous Robot Path Planning” IEEE International Conference on Neural Network (06, 1987) pp. IV507–IV515.Google Scholar
25.Lin, C.S. and Wann, C.D.,, “A Parallel Processing Model for Robot Path Planning on Grid Terrains”, Int. J. Robotics and Automation 6, No. 1, 1–11 (1981).Google Scholar
26.Chan, R.H.T., Tam, P.K.S., and Leung, D.N.K., “A Neural Network Approach for Solving the Path Planning Problem” IEEE International Symposium on Circuits and Systems, 05 3–6, 1993, Chicago, U.S.A.) (1993) pp. 2452–2457.Google Scholar
27.Soult, T.E., “Dynamic Digital Distance Maps in Two Dimensions” IEEE Transactions on Robotics and Automation 6, No. 5, 590–597 (10, 1990).Google Scholar