论文标题
用单个或反物距离测量的定位
Localization with Single or Antipodal Distance Measurements
论文作者
论文摘要
给定一个多边形的工作区$ W $，在$ w $内放置的深度传感器$ p =（x，y）$内部$ w $，并以方向$θ$定向$ d = h（x，y，y，θ）$之间的距离（x，y，θ）$在$ w $的边界之间的最接近$ w $的最接近点，沿$ w $沿着$ p $ $ p $在$ ph $ ch $θ$θ$θ$中。 We study the following problem: For a polygon $W$ with $n$ vertices, possibly with holes, preprocess it such that given a query real value $d> 0$, one can efficiently compute the preimage $h^{-1}(d) \subset W\times \mathbb{S}^1$, namely determine all the possible poses (positions and orientations) of a depth sensor placed in $ w $将以产量敏感的方式产生阅读$ d $。我们描述了这样一种输出敏感的数据结构，该数据结构以$ O（k \ log n）$时间回答查询，其中$ k $是构成答案的低度代数曲线的顶点和最大弧。我们还获得了更有用的情况（缩小可能的姿势集）的类似结果，其中传感器从$ W $中的同一点执行了两个对抗原深度测量值。然后，我们描述了相同两个问题的更简单的数据结构，其中我们采用了$ w \ times \ mathbb {s}^1 $的分解，而查询时间相对于此分解而言对输出敏感。我们针对这些后一种结构的软件实施是开源的，并且可以公开使用。尽管机器人定位通常是通过探索放置在环境点的传感器的完整可见性多边形来实现的，但我们在这里提出的方法只需少量的深度测量，这是有利的，因为它可以使用廉价的传感器，并且还可以节省存储和通信成本。
Given a polygonal workspace $W$, a depth sensor placed at point $p=(x,y)$ inside $W$ and oriented in direction $θ$ measures the distance $d=h(x,y,θ)$ between $p$ and the closest point on the boundary of $W$ along a ray emanating from $p$ in direction $θ$. We study the following problem: For a polygon $W$ with $n$ vertices, possibly with holes, preprocess it such that given a query real value $d> 0$, one can efficiently compute the preimage $h^{-1}(d) \subset W\times \mathbb{S}^1$, namely determine all the possible poses (positions and orientations) of a depth sensor placed in $W$ that would yield the reading $d$, in an output-sensitive fashion. We describe such an output-sensitive data structure, which answers queries in $O(k \log n)$ time, where $k$ is the number of vertices and maximal arcs of low degree algebraic curves constituting the answer. We also obtain analogous results for the more useful case (narrowing down the set of possible poses), where the sensor performs two antipodal depth measurements from the same point in $W$. We then describe simpler data structures for the same two problems, where we employ a decomposition of $W\times \mathbb{S}^1$, and where the query time is output-sensitive relative to this decomposition. Our software implementation for these latter structures is open source and publicly available. Although robot localization is often carried out by exploring the full visibility polygon of a sensor placed at a point of the environment, the approach that we propose here opens the door to sufficing with only few depth measurements, which is advantageous as it allows for usage of inexpensive sensors and could also lead to savings in storage and communication costs.
