Abstract
Analog VLSI provides a convenient and high-performance engine for robot path planning. Laplace's equation is a useful formulation of the path-planning problem; however, digital solutions are very expensive. Since high precision is not required, an analog approach is attractive. A resistive network can be used to model the robot's domain with various boundary conditions for the source, target, and obstacles. A gradient descent can then be traced through the network by comparing node voltages. We built two analog CMOS VLSI chips to investigate the feasibility of this technique. Design issues included the choice of resistive element, tessellation of the domain, programming of the network, and readout of the settled network. Both chips can be connected to a standard VME bus interface to permit their use as coprocessors in otherwise digital systems.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ronald C. Arkin, “Towards cosmopolitan robots: Intelligent navigation in extended man-made environments,” Technical Report 87-80, COINS Department, University of Massachusetts, 1987.
Jérôme Barraquand, Bruno Langlois, and Jean-Claude Latombe, “Robot motion planning with many degrees of freedom and dynamic constraints,”Proc. Fifth Int. Symp. Robotics Research, 1989.
John F. Canny and Ming C. Lin, “An opportunistic global path planner,”Proc. 1990 IEEE Int. Conf. Robotics and Automation, pp. 1554–1559, 1990.
Oussama Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,”Proc. 1985 IEEE Int. Conf. Robotics and Automation, pp. 500–505, 1985.
Daniel E. Koditschek, “Exact robot navigation by means of potential functions: Some topological considerations,”Proc. 1987 IEEE Int. Conf. Robotics and Automation, pp. 1–6, 1987.
Bruce H. Krogh, “A generalized potential field approach to obstacle avoidance control,” inRobotics Research: The Next Five Years and Beyond, Society of Manufacturing Engineers, 1984.
C.I. Connolly, J.B. Burns, and R. Weiss, “Path planning using Laplace's equation,”Proc. 1990 IEEE Int. Conf. Robotics and Automation, pp. 2102–2106, 1990.
C.I. Connolly, “Applications of harmonic functions to robotics,”Proc. 1992 IEEE Int. Symp. Intelligent Control, 1992.
D.L. Slotnick, W.C. Borck, and R.C. McReynolds, “The SOLOMON computer,”AFIPS 1962 Fall Joint Computer Conf., Spartan Books, pp. 97–107, 1962.
H.S. Stone,High-Performance Computer Architecture, Addison-Wesley: Reading, MA, 1987.
T. Lozano-Pérez, “Automatic planning of manipulator transfer movements,”IEEE Trans. Systems, Man, Cybernet., Vol. SMC-11, pp. 681–698, 1981.
G.D. McCann and C.H. Wilts, “Application of electric-analog computers to heat-transfer and fluid-flow problems,”J. Appl. Mech., Vol. 16, pp. 247–258, 1949.
J.J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,”Proc. Nat. Acad. Sci., 1982.
B.K.P. Horn and B.G. Schunck, “Determining optical flow,”Artificial Intelligence, 1981.
J. Hutchinson, C. Koch, J. Luo, and C. Mead, “Computing motion using analog and binary resistive networks,”IEEE Computer, pp. 52–63, March 1988.
C. Mead,Analog VLSI and Neural Systems, Addison-Wesley: Reading, MA, 1989.
C. Mead and M. Ismail, eds.,Analog VLSI Implementation of Neural Systems, Kluwer: Boston, 1989.
C.I. Connolly, “On the applications of harmonic functions to robotics,” Technical Report, Laboratory for Perceptual Robotics, COINS Department, University of Massachusetts at Amherst, 1991.
L. Tarassenko and A. Blake, “Analogue computation of collision-free paths,”Proc. 1991 IEEE Int. Conf. Robotics and Automation, Sacramento, CA, pp. 540–545, 1991.
N. Weste and K. Eshragian,Principles of CMOS VLSI Design—A Systems Perspective, Addison-Wesley: Reading, MA, 1985.
J.P. Lazzaro, S. Ryckebusch, M.A. Mahowald, and C.A. Mead, “Winner-take-all networks ofO(N) complexity,” Caltech Computer Science Department Technical Report, Caltech-CS-TR-21-88, 1989.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Stan, M.R., Burleson, W.P., Connolly, C.I. et al. Analog VLSI for robot path planning. Journal of VLSI Signal Processing 8, 61–73 (1994). https://doi.org/10.1007/BF02407111
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02407111