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 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]
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]
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-Reconfigurable Robots, International
Journal of Computational Geometry & Applications (IJCGA), Vol. 21, No. 2,
pp. 131-155 (2011).
DOI: 10.1142/S0218195911003585
[PDF]