Dynamic Shortest Path Algorithms and their Applications

在机器人、地理信息系统、导航、社交网络和传感器网络等许多应用中，环境是动态的。物体/实体可以移动、消失、出现甚至改变形状。为静态环境设计的传统最短路径算法要么不适用，要么需要频繁的重新计算，从而变得效率低下。动态最短路径问题的研究主要集中在图（或超图）领域。这些实例允许插入和/或删除图边和/或更改权重。完全动态算法允许边的插入和删除；部分动态算法允许插入或删除，但不能同时进行。对于完全动态算法和部分动态算法都有相应的结果。在前人工作的基础上，我们对求解几何问题的动态最短路径算法很感兴趣。例如，对象（用于最短路径计算的障碍物）可能只存在于固定的时间间隔[Ts， Te]，即，对象在时间Ts出现，在时间Te消失。物体的形状可能会随着时间的推移而改变（比如，从一个点连续增长到越来越大的圆圈——当人们想要模拟不确定性时，就会出现这样的问题）。另一类有趣的动态最短路径问题出现在与时间相关的图或网络中，其中边的代价（即边的移动时间）作为时间的函数而变化，因此两个节点s和d之间的最短路径可能随着时间而变化。我们已经研究了用常用的傅氏距离法测量多边形曲线的相似度。在计算机图形学、模式识别、聚类、地理信息系统和结构生物学、运动场景分析、人类运动、监视和动物行为等领域都会出现多边形曲线之间的相似性问题。我们发现和/或改进了一些令人兴奋的和自然的优化问题，涉及到fr<s:1>切特距离。解决方案通常涉及解决特定的最短路径问题。为了解决几个新的优化和参数化问题，我们将遇到几何动态最短路径问题。这些问题的解也有独立的意义并且使我们能够得到这些fr<s:1>距离问题的解。

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.