On finding energy-minimizing paths on terrains

Zheng Sun, John H. Reif

Research output: Contribution to journalJournal articlepeer-review

71 Citations (Scopus)


In this paper, we discuss the problem of computing optimal paths on terrains for a mobile robot, where the cost of a path is defined to be the energy expended due to both friction and gravity. The physical model used by this problem allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. The 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 optimal paths on terrains under this model. With some additional assumptions, we present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared with previous results using the same approach, this algorithm improves the time complexity by using 1) a discretization with reduced size, and 2) an improved discrete algorithm for finding optimal paths in the discretization. We present some experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for a more difficult variant of the problem due to less restricted assumptions.

Original languageEnglish
Pages (from-to)102-114
Number of pages13
JournalIEEE Transactions on Robotics
Issue number1
Publication statusPublished - Feb 2005
Externally publishedYes

Scopus Subject Areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Computational geometry
  • Mobile-robot motion planning
  • Optimization
  • Road vehicles


Dive into the research topics of 'On finding energy-minimizing paths on terrains'. Together they form a unique fingerprint.

Cite this