Suppose an agent asserts that it will move through an environment in some way. When the agent executes its motion, how does one verify the claim? The problem arises in a range of contexts including in validating safety claims about robot behavior, applications in security and surveillance, and for both the conception and the (physical) design and logistics of scientific experiments. Given a set of feasible sensors to select from, we ask how to choose sensors optimally in order to ensure that the agent's execution does indeed fit its pre-disclosed itinerary. Our treatment is distinguished from prior work in sensor selection by two aspects: the form the itinerary takes (a regular language of transitions) and that families of sensor choices can be grouped as a single choice. Both are intimately tied together, permitting construction of a product automaton because the same physical sensors (i.e., the same choice) can appear multiple times. This paper establishes the hardness of sensor selection for itinerary validation within this treatment, and proposes an exact algorithm based on an ILP formulation that is capable of solving problem instances of moderate size. We demonstrate its efficacy on small-scale case studies, including one motivated by wildlife tracking.
翻译:假设一个代理人声称它将以某种方式在环境中移动。 当该代理人执行运动时, 如何核查其主张? 问题出现于一系列背景下, 包括验证机器人行为、 安全和监视应用的安全主张, 以及科学实验的孕期和( 物理)设计和物流。 如果有一组可行的传感器可以从中选择, 我们询问如何最佳地选择传感器, 以确保该代理人的执行确实符合其事先公布的行程。 我们的处理方式不同于先前在传感器选择方面采用的两个方面: 行程的形式( 一种正常的过渡语言), 以及传感器选择的家庭可以归为单一的选择。 两者都紧密相连, 允许建造一个产品自动图, 因为相同的物理传感器( 相同选择) 可以多次出现。 本文确定了在这种处理中进行行程验证的传感器选择的难度, 并提出了一种精确的算法, 其依据的ILP 配方能够解决中度问题的例子。 我们展示了它对于小规模案例研究的有效性, 包括由野生动物追踪驱动的。