Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths
Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths
复制标题
最小约束去除路径搜索方法的计算权衡
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kostas E. Bekris
中科院分区：
文献类型：
--
作者：
A. Krontiris;Kostas E. Bekris
路径规划的典型目标是寻找最短的可行路径。然而，考虑到障碍等制约因素的存在，很多时候可能没有解决办法。在这些情况下，最小约束移除问题要求从状态空间移除约束的最小集合，以找到解。不幸的是，最小约束去除路径不表现出动态规划属性，即，最优解的子集不一定是最优的。因此，寻找这样的解决方案在计算上是昂贵的。这导致了近似方法的出现，这种方法平衡了计算解的成本和质量。这项工作调查了在这种情况下的替代方案，并根据这种权衡来评估它们的性能。遵循有限长度方法的解决方案，即搜索直到一定长度的路径，似乎在最小化约束、计算成本和路径长度之间提供了良好的平衡。
The typical objective of path planning is to find the shortest feasible path. Many times, however, there may be no solution given the existence of constraints, such as obstacles. In these cases, the minimum constraint removal problem asks for the minimum set of constraints that need to be removed from the state space to find a solution. Unfortunately, minimum constraint removal paths do not exhibit dynamic programming properties, i.e., subsets of optimum solutions are not necessarily optimal. Thus, searching for such solutions is computationally expensive. This leads to approximate methods, which balance the cost of computing a solution and its quality. This work investigates alternatives in this context and evaluates their performance in terms of such tradeoffs. Solutions that follow a bounded-length approach, i.e., searching for paths up to a certain length, seem to provide a good balance between minimizing constraints, computational cost and path length.