find a bounded suboptimal solution

find a bounded suboptimal solution which considers both
traveling time and sensing time with respect to a pre-defined
set of sensing positions. However, the problem of selecting
the initial set of sensing positions remains open and the
approach presents scalability issues when the cardinality of
the set is increased.
In the past decades, there has been extensive work on
problems which are closely related to the one addressed in
this paper. Ignoring the cost associated to sensing actions, our
problem could be reduced to the Generalized Covering Sales￾man Problem [8], whose instances are solved by generating
paths from which the whole environment can be observed.
A similar problem is solved in [9], where an approach based
on mixed integer linear programming is used for finding a
surveillance route for a mobile camera.
Neglecting the cost associated to the movements of the
robot, our problem could be reduced to an Art Gallery
Problem [10] or to a View Planning Problem [11]. The
art gallery problem is NP-hard in its most common vari￾ants and view planning is isomorphic to the Set Covering
Problem [12], a well known NP-complete problem. This
family of problems has been extensively studied over the
past decades [13], [14], but the algorithms proposed for
optimal solutions are effective under restricted assumptions,
such as not considering occlusions in the field of view of
the sensors [15], or work only when the number of possible
sensing positions is relatively small [16], [17]. There exist,
however, efficient algorithms for calculating approximated
solutions [18] for problem instances with a large number of
possible sensing positions. The solutions described above,
however, present two major drawbacks in our context: First,
they are mostly concerned with camera placement problems,
which means that they rarely consider limited field of view;
second, they do not consider the cost of moving from one
sensor position to the next. On the other hand, assuming
known sensing positions, we would still need to solve a
(Metric) Traveling Salesman Problem, that is, we should
find the shortest tour that connects all the sensing positions.
This is a well-known NP-hard problem, but it is possible to
optimally solve very large TSP instances, with thousands of
locations

結果 (中文) 1:

找到一个有界的次优解，认为两个旅行时间和遥感对预定义的时间遥感的职位设置。然而，选择问题传感位置的初始集保持打开状态，方法提出了可扩展性问题时的基数增加了一套。在过去几十年来，出现了广泛的工作上一个解决密切相关的问题本文。忽略在传感的行为，相关的成本我们问题可以简化为广义覆盖销售人解决 [8]，其实例是通过生成从中可以观察到整个环境的路径。类似的问题解决 [9] 中的方法在混合整数线性规划用于发现移动的摄像机的监控路线。忽略的运动相关的成本机器人，我们的问题可以减少到一个艺术画廊[10] 的问题或规划问题 [11] 视图。的艺术画廊问题是 NP 难的在其最常见的变异蚂蚁和视图规划是同构于设置覆盖问题 [12]，众所周知的 NP 完全问题。这在广泛研究了家庭的问题过去几十年来 [13] [14]，但提出的算法最佳解决方案是有效限制在假设下，例如，可以不考虑闭塞的视野[15]，传感器或工作只有当数的可能传感的位置是相对较小 [16] [17]。存在，然而，有效的算法，计算近似一大批问题实例解决方案 [18]可能的遥感位置。上文所述的解决方案然而，在我们方面呈现两个主要缺陷︰ 第一，他们大多关注与照相机安置问题，这意味着，他们很少考虑有限的视野;第二，他们不认为从一个成本传感器定位到下一步。另一方面，假设已知遥感的立场，我们仍需解决（米制）货郎担问题，那就是，我们应找到最短的旅行，连接所有遥感的职位。这是一个著名的 NP 难问题，但它是可能的以最佳方式解决非常大量的 TSP 实例，与成千上万的地点

結果 (中文) 3:

找到一个有界次优的解决方案，同时考虑旅行时间和感知时间相对于一个预定义的传感位置集。然而，选择的问题传感位置的初始组保持打开和方法提出了可扩展性的问题时，基数增加了设置。在过去的几十年里，已经有大量的工作问题是密切相关的一个解决本文。忽略与传感行动相关的成本问题可以减少到广义覆盖销售￾男人问题[ 8 ]，其实例的求解发电可以观察到整个环境的路径。类似的问题解决在[ 9 ]，其中一种方法为基础的关于混合整数线性规划的一个移动相机的监视路径。忽略了相关的成本的运动机器人，我们的问题可以减少到一个艺术画廊问题[ 10 ]或一个视图规划问题[ 11 ]。这个美术馆问题是其最常见的变异￾蚂蚁和景观规划的NP是同构的集合覆盖问题[ 12 ]，一个众所周知的NP-完全问题。这家庭的问题已被广泛研究过去的几十年[ 13 ]，[ 14 ]，但提出的算法在受限制的假设下，最优解是有效的，如不考虑遮挡在视野中的该传感器[ 15 ]，或工作时，可能的数量传感位置相对较小[ 16 ]，[ 17 ]。存在，然而，有效的算法计算近似解决方案[ 18 ]的问题的情况下，大量的可能的敏感位置。上面描述的解决方案，然而，在我们的背景下，提出了两个主要的缺点：第一，他们主要关心的是相机放置问题，这意味着他们很少考虑有限的视野；第二，他们不考虑从一个移动的成本传感器位置到下一个。另一方面，假设已知的传感位置，我们还需要解决一个（公制）旅行商问题，也就是说，我们应该寻找连接所有敏感位置的最短的旅行。这是一个众所周知的NP-难的问题，但它是可能的最佳解决非常大的问题的实例，有成千上万的位置