Papers by Reif on Motion Planning and Kinodynamics in Robotics (31 papers)

  1. John H. Reif, Complexity of the Mover's Problem and Generalizations. 20th Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1979, pp. 421-427. [PDF] Published as Complexity of the Generalized Mover's Problem, Chapter 11 in Planning, Geometry and Complexity of Robot Motion, Jacob Schwartz, ed., Ablex Pub., Norwood, NJ, 1987, pp. 267-281. [PDF]
  2. John H. Reif and M. Sharir, Motion Planning in the Presence of Moving Obstacles, 26th Annual IEEE Symposium on Foundations of Computer Science, Portland, OR, October 1985, pp. 144-154. Published in Journal of the ACM (JACM), 41:4, July 1994, pp. 764-790. [PDF] or [PostScript] [PDF]
  3. John H. Reif and James A. Storer, Shortest Paths in the plane with polygonal obstacles, Journal of the ACM(JACM) 41:5, September, 1994, pp. 982-1012. [PDF]
  4. John H. Reif and James A. Storer, Minimizing Turns for Discrete Movement in the Interior of a Polygon, IEEE Journal of Robotics and Automation, Vol. 3, No. 3, June 1987, pp. 182-193. [PDF]
  5. John Canny and John H. Reif, New Lower Bound Techniques for Robot Motion Planning Problems. 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, October 1987, pp. 49-60. [PDF]
  6. John Canny, B. Donald, John H. Reif and Patrick G. Xavier. On the Complexity of Kinodynamic Planning. 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, NY, October 1988, pp. 306-316. Published as Kinodynamic Motion Planning, Journal of the ACM, Vol 40(5), November 1993, pp. 1048-1066. [PDF]
  7. John H. Reif and S. Tate, Continuous Alternation: The Complexity of Pursuit in Continuous Domains, Special Issue on Computational Robotics: the Geometric Theory of Manipulation, Planning and Control, Algorithmica, Vol. 10, pp. 151-181, 1993. [PostScript] [PDF]
  8. John H. Reif and S. Tate, Approximate Kinodynamic Planning Using L2-norm Dynamic Bounds. Duke University Technical Report CS-1990-13, 1989. Published in Computers and Mathematics with Applications, Vol. 27, No.5, pp.29-44, March 1994. [PostScript] [PDF]

1.  John H. Reif, A Survey on Advances in the Theory of Computational Robotics. Proceedings of the Fourth Workshop of Adaptive Systems Control Theory, Princeton, NJ, 1986. Also as Chapter in Book: Adaptive and Learning Systems: Theory and Applications, Princeton, NJ (edited by K.S. Narendra), Plenum Press, New York, NY, pp. 421--427 1986. [PDF]

9.  John Canny, A. Rege, and John H. Reif, An Exact Algorithm for Kinodynamic Planning in the Plane. 6th Annual ACM Symposium on Computational Geometry, Berkeley, CA, June 1990, pp. 271-280. [PDF] Published in Discrete and Computational Geometry, Vol. 6, 1991, pp. 461-484. [PDF]

10.                 John H. Reif and Hongyan Wang, On Line Navigation Through Regions of Variable Densities. ARO Computational Geometry Workshop, Raleigh, North Carolina, October, 1993. Rewritten as On-Line Navigation Through Weighted Regions. [PostScript] [PDF]

  1. John H. Reif and Hongyan Wang, Social Potential Fields: A Distributed Behavioral Control for Autonomous Robots, Workshop on Algorithmic Foundations of Robotics (WAFR'94), San Francisco, California, February, 1994; The Algorithmic Foundations of Robotics, A.K.Peters, Boston, MA. 1995, pp. 431-459. Published in Robotics and Autonomous Systems, Vol. 27, no.3, pp.171-194, (May 1999). [PostScript] [PDF]
  2. John H. Reif and James A. Storer, 3-Dimensional Shortest Paths in the Presence of Polygonal Obstacles. 13th Symposium on Mathematical Foundations of Computer Science, (Edited by Michal Chytil, Ladislav Janiga, V‡clav Koubek) Czechoslovakia, August 29-September 2, 1988, pp. 85-92. Published as A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions. Journal of the ACM(JACM), Vol. 41, No. 5, Sept. 1994, pp. 1013-1019. [PDF]
  3. Erol Gelenbe, Nestor Schmajuk, John Staddon, and John H. Reif, Autonomous Search and the Search for Robots and Mines: A Survey, Robotics and Autonomous Systems, Vol. 22, pp. 23-33. (November 1997). [PostScript] [PDF]
  4. John H. Reif, Toward Autonomous Robots: Robust, Adaptive and Dynamic Motion, 19th NSF Design and Manufacturing Grantees Conference, Monterrey, Mexico, Jan 1998. [PostScript] [PDF]
  5. John H. Reif and Hongyan Wang, Nonuniform Discretization for Kinodynamic motion planning and its applications, Workshop on Foundations of Robotics, Toulouse, France, July 1996, 97-112. Published in SIAM Journal of Computing (SICOMP), Volume 30, No. 1, pp. 161-190, (2000). [PostScript] [PDF]
  6. John H. Reif and Zheng Sun, Nano-Robotics Motion Planning and Its Applications in Nanotechnology and Biomolecular Computing, NSF Design and Manufacturing Grantees Conference, Jan 5-8, 1999. [HTML]
  7. John H. Reif and Hongyan Wang, The Complexity of the Two Dimensional Curvature-Constrained Shortest-Path Problem, Third International Workshop on Algorithmic Foundations of Robotics (WAFR98), Pub. by A. K. Peters Ltd, Houston, Texas, pp. 49-57, June, 1998. [PostScript] [PDF]
  8. John H. Reif and Zheng Sun, The Computational Power of Frictional Mechanical Systems, Third International Workshop on Algorithmic Foundations of Robotics, (WAFR98), Pub. by A. K. Peters Ltd, Houston, Texas, pp. 223-236, Mar. 5-7 1998. Published as On Frictional Mechanical Systems and Their Computational Power, SIAM Journal of Computing(SICOMP), Vol. 32, No. 6, pp. 1449-1474, (2003). [PDF] or [PDF] Talk slides: [HTML]
  9. John H. Reif and Zheng Sun. An efficient approximation algorithm for weighted region shortest path problem. In Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics (WAFR2000), A. K. Peters Ltd Publishers, Hanover, New Hampshire, pp. 191-203, Mar. 16-18 2000. [PDF] [PostScript]. Published as Zheng Sun and John H. Reif, On Finding Approximate Optimal Paths in Weighted Regions, Journal of Algorithms, Volume 58, Number 1, pp. 1-32, January 2006. [PDF]
  10. John H. Reif and Zheng Sun. Movement planning in the presence of flows. In Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS2001), volume 2125 of Lecture Notes in Computer Science, pp. 450-461, Brown University, Providence, RI, August 8-10, (2001). Published in Algorithmica, Volume 39, Number 2, pp. 127-153, February 2004. [PDF] or [PDF]. Talk: [PDF]

21.                 Zheng Sun and John H. Reif. BUSHWHACK: An approximation algorithm for minimal paths through pseudo-Euclidean spaces. In Proceedings of the 12th Annual International Symposium on Algorithms and Computation(ISAAC01), Christchurch, New Zealand, Dec 19-21, 2001, Volume 2223 of Lecture Notes in Computer Science, pp. 160-171, Dec, 2001. Published in IEEE Transactions on Systems, Man, and Cybernetics (SMC), Part B: Cybernetics, Vol. 37, No. 4, pp. 925-936 (2007). [PDF] [PDF]

22.                 Zheng Sun and John H. Reif, On Finding Energy-minimizing Paths on Terrains for a Mobile Robot, 2003 IEEE International Conference on Robotics and Automation(ICRA2003), Taipei, Taiwan, pp. 3782-3788, May 12-17, 2003. Published in IEEE Transaction on Robotics, Volume: 21, Issue: 1, February 2005, pp. 102-114. [PDF]

23.                 D. Hsu, T. Jiang, John H. Reif, and Zheng Sun, The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners, 2003 IEEE International Conference on Robotics and Automation(ICRA2003), Taipei, Taiwan, Vol.3, pp. 4420 – 4426, Sept. 14-19, 2003. Published as Zheng Sun, D. Hsu, T. Jiang, H. Kurniawati, and J.H.Reif, Narrow Passage Sampling for Probabilistic Roadmap Planning, IEEE Transactions on Robotics, Volume 21, No. 6, Dec. 2005. pp. 1105–1115. [PDF]

24.                 John H. Reif and Zheng Sun, On Boundaries of Highly Visible Spaces and Applications, 14th Symposium on Fundamentals of Computation Theory, Malmš Hšgskola, Sweden, August 12-15, 2003, Springer-Verlag Lecture Notes in Computer Science, 2003. Invited paper published in Theoretical Computer Science, Volume 354, Issue 3, (4 April 2006), pp. 379-390. [PDF] [PDF]

  1. Zheng Sun and John H. Reif, Adaptive and Compact Discretization for Weighted Region Optimal Path Finding. 14th Symposium on Fundamentals of Computation Theory, Malmš Hšgskola, Sweden, August 12-15, 2003, Springer-Verlag Lecture Notes in Computer Science, Vol. 2751, pp. 258-270, 2003. [PostScript] [PDF]
  2. John H. Reif and Sam Slee, Asymptotically Optimal Kinodynamic Motion Planning for Self-Reconfigurable Robots, Seventh International Workshop on the Algorithmic Foundations of Robotics (WAFR2006), NYC, New York, July 16-18, 2006. Published in Algorithmic Foundation of Robotics VII, Springer Tracts in Advanced Robotics (Edited by S. Akella, N.M. Amato, W.H. Huang, B. Mishra), Volume 47, Springer-Verlag Berlin, pp. 457–472, (Aug 2008). [PDF] Published as Asymptotically Optimal Kinodynamic Motion Planning for a Class of Lattice-Style Modular Self-ReconŽgurable Robots, International Journal of Computational Geometry & Applications (IJCGA), Vol. 21, No. 2, pp. 131-155 (2011). DOI: 10.1142/S0218195911003585 [PDF]

27.                 John H. Reif and Sam Slee, Optimal Kinodynamic Motion Planning for Self-ReconŽgurable Robots Between Arbitrary 2D ConŽgurations, Robotics: Science and Systems Conference, Georgia Institute of Technology, Atlanta, GA, June 27-30, 2007. [PDF]

28.                 Urmi Majumder and John H. Reif, A Framework for Designing Novel Magnetic Tiles Capable of Complex Self-Assemblies, Conference on Unconventional Computation, Vienna, Austria, Aug 25-26, 2008, Unconventional Computing, Lecture Notes in Computer Science number 105633, Springer, Berlin Heidelberg. Conference Version: [PDF]. Revised paper submitted for journal publication as Barcoded Magnetic Tiles for Complex Programmable Assemblies. Full Paper: [PDF]

29.                 John H. Reif, Mechanical Computation: itÕs Computational Complexity and Technologies, invited chapter, Encyclopedia of Complexity and System Science (edited by Robert A. Meyers), Springer (2009) ISBN: 978-0-387-75888-6. A revised version also appears as Mechanical Computing: The Computational Complexity of Physical Devices, invited chapter, Encyclopedia of Complexity and System Science (edited by Andrew Spencer), Springer-Verlag, Heidelberg, Germany (2013) [PDF]

30.                 Sam Slee and John H. Reif, Robomotion: Scalable, Physically Stable Locomotion for Self-Reconfigurable Robots, Workshop on the Algorithmic Foundations of Robotics(WAFR 2010), Singapore, Springer (Dec. 13-15 2010). [PDF]