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

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

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ö Högskola, 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]