Papers by Reif on Motion Planning and Kinodynamics in Robotics (30 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 J.A. Storer, Shortest Paths in Euclidean Space with Polyhedral Obstacles. Symposium on Mathematical Foundations of Computer Science, Czechoslovakia, August 1988, pp. 85-92. Published as 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 J.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. J. 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. J. Canny, B. Donald, John H. Reif and pp. 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]

9. John H. Reif, A Survey on Advances in the Theory of Computational Robotics. Proceedings of the Fourth Workshop of Adaptive Systems Control Theory as Adaptive and Learning Systems: Theory and Applications, K.S. Narendra, ed., Plenum Press, New York, NY, 1986. [PDF]

10.         J. 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]

11.         John H. Reif and H. 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]

12.         John H. Reif and H. 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]

13.         John H. Reif and J. Storer, 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]

14.         E. Gelenbe, N.Schmajuk, J. 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]

15.         John H. Reif, Robust, Adaptive and Dynamic Robotic Motion Planning, 19th NSF Design and Manufacturing Grantees Conference, Monterrey, Mexico, Jan 1998. [PostScript] [PDF]

16.         John H. Reif and H. 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]

17.         John H. Reif and Z. Sun, Nano-Robotics Motion Planning and Its Applications in Nanotechnology and Biomolecular Computing, NSF Design and Manufacturing Grantees Conference, Jan 5-8, 1999. [HTML]

18.         John H. Reif and H. 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]

19.         John H. Reif and Z. 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]

20.         John H. Reif and Z. 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 Z. 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]

21.         John H. Reif and Z. 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]

22.         Z. 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]

23.         Z. 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]

24.         D. Hsu, T. Jiang, John H. Reif, and Z. 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 Z. 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]

25.         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]

26.         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].

27.         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), to appear (2010). [PDF]

28.         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]

29.         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. Published in Unconventional Computing, Lecture Notes in Computer Science number 105633, Springer, Berlin Heidelberg. Conference Version: [PDF]. Published as Beyond Molecular Computing:  Novel Magnetic Tiles for Complex Assemblies, Invited paper, special issue "Computing with Molecules" of Natural Computing, (2009). Full Paper: [PDF]

30.         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. [PDF]