**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. Published online (April 2017). [PDF] [PDF] DOI:10.1007/978-3-642-27737-5_325-4.
- 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]