Publications [#236998] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Sun, Z; Reif, J, On energy-minimizing paths on terrains for a mobile robot, in 2003 IEEE International Conference on Robotics and Automation(ICRA2003), Proceedings IEEE International Conference on Robotics and Automation, vol. 3 (December, 2003), pp. 3782-3788, IEEE [pdf]
   (last updated on 2026/01/14)

   Abstract:
   In this paper we discuss the problem of computing optimal paths on terrains for a mobile robot. The cost of a path is defined to be the energy expended due to both friction and gravity. The model allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. This model is interesting and challenging as it incorporates constraints found in realistic situations and these constraints affect the computation of optimal paths. We give some upper and lower bound results on the combinatorial size of energy-minimizing paths on terrains. We also present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared to previous results with the same approach, this algorithm improves the time complexity by using (a) a discretization with reduced size, and (b) an improved discrete algorithm for finding optimal paths in the discretization. We present some preliminary experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for the same model but under less restricted assumptions.