Dynamic Shortest Path Algorithms and their Applications

在机器人、地理信息系统、导航、社交网络和传感器网络等许多应用中，环境是动态的。物体/实体可以移动、消失、出现甚至改变形状。为静态环境设计的传统最短路径算法要么不适用，要么需要频繁的重新计算，从而变得效率低下。

In many applications arising e.g., in Robotics, GIS, Navigation, Social Networks, and Sensor Networks, environments are dynamic. Objects/entities may move, disappear, appear and even change shape. Traditional shortest path algorithms, designed for static environments, would either not be applicable or require frequent recomputations and thus become inefficient. Most activity for dynamic shortest path problems has been in the area of graph (or hyper-graph). These instances allow for graph edges to be inserted and/or deleted and/or weights to be changed. Fully dynamic algorithms allow edges to be both inserted and deleted; partially dynamic algorithms allow for either insertions or deletions, but not both. Results exist for both fully and partially dynamic algorithms. Building on, and motivated by, previous work, we are interested in dynamic shortest path algorithms for solving geometric problems. For example, objects (obstacles for the shortest path computation) may only exist for a fixed time interval [Ts, Te], i.e., the object appears at time Ts and disappears at time Te. Objects may change shape over time (say grow continuously from a point to larger and larger circles - such problems arise when one wants to model uncertainties). Another interesting class of dynamic shortest paths problems arises in time-dependent graphs or networks, where the costs of edges (that is, edge travel times) vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. We have already studied similarities of polygonal curves measured via the frequently used Fréchet Distance. Similarity problems between polygonal curves arise e.g. in Computer Graphics, Pattern Recognition, Clustering, GIS and structural biology, sports scene analysis, human movement, surveillance, and animal behavior. We discovered and/or improved upon some exciting and natural optimization problems involving the Fréchet Distance. The solution often involved solving particular shortest path problems. To solve several new optimization and parameterization problems using the Fréchet Distance and its variants, we will encounter geometric dynamic shortest path problems. Solutions to these are also of independent interest and will enable us to obtain also solutions to these Fréchet Distance problems.