**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 *L*2-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]

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

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

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

12.
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, Vclav 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]

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

14.
John H. Reif, Toward Autonomous Robots: Robust, Adaptive and Dynamic Motion, 19th NSF
Design and Manufacturing Grantees Conference, Monterrey, Mexico, Jan 1998. [PostScript] [PDF]

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

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

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

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

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

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

- 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] - 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]
- 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]
- John H. Reif and Zheng Sun,
On Boundaries of Highly Visible Spaces and Applications, 14th Symposium
on Fundamentals of Computation Theory, Malm Hgskola,
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]

25.
Zheng Sun and John H.
Reif, Adaptive and Compact Discretization for Weighted Region Optimal Path
Finding. 14th Symposium on Fundamentals of Computation Theory, Malm Hgskola, Sweden, August 12-15, 2003, Springer-Verlag Lecture Notes in Computer Science, Vol. 2751, pp.
258-270, 2003. [PostScript] [*PDF*]

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

- 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]
- 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]
- John H. Reif, Mechanical
Computation: itÕs Computational Complexity and Technologies, invited
chapter, Encyclopedia of Complexity and System Science (edited by Robert
A. Meyers), in section: Unconventional
Computing (section editor: Andrew Adamatzky), Springer-Verlag, New York (2009), pp. 1821-1836, ISBN:
978-0-387-75888-6. DOI: 10.1007/978-0-387-30440-3_325.
[HTML]
[PDF] [PDF]. 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. Springer-Verlag, Heidelberg, Germany. Published online
(2013) and in print in pp. 5466-5482 (2014). [HTML]
[PDF] [PDF] [PDF] A further revised version also appears
as Mechanical
Computing: The Computational Complexity of Physical Devices, invited
chapter, pp. 1-21, Encyclopedia
of Complexity and System Science (edited by R.A.), Springer-Verlag,
Heidelberg, Germany. Springer-Verlag,
Heidelberg, Germany (April 2017) [PDF] [PDF] DOI:
10.1007/978-3-642-27737-5_325-4. Also appearing as Chapter 2 in book Unconventional Computing, pp. 35-55, (2018). DOI: 10.1007/978-1-4939-6883-1_325
[PDF] [PDF]
- Sam Slee and John H.
Reif, 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]