I. Introduction
Many minimum-time planning problems in robotics in-herently involve time-costs that are non-static. In terms of finding shortest paths on graphs, this means that edge traversal time is not a scalar value, but instead is a function that varies over time. The importance of developing shortest path algorithms for non-static travel times is well recognised, and somewhat surprisingly, has been studied for over 50 years [2]. In comparison to static shortest path problems, progress in developing a theoretical understanding of the time-dependent shortest path (TDSP) problem has proved far more elusive. Our goal is to explore relatively recent theoretical results in an effort to develop practical algorithms for robotics applications.