Sensor information monotonicity in disambiguation protocols

Abstract

Previous work has considered the problem of swiftly traversing a marked traversal-medium where the marks represent probabilities that associated local regions are traversable, further supposing that the traverser is equipped with a dynamic capability to disambiguate these regions en route. In practice, however, the marks are given by a noisy sensor, and are only estimates of the respective probabilities of traversability. In this paper, we investigate the performance of disambiguation protocols that utilize such sensor readings. In particular, we investigate the difference in performance when a disambiguation protocol employs various sensors ranked by their estimation quality. We demonstrate that a superior sensor can yield superior traversal performance—so called Sensor Information Monotonicity. In so doing, we provide to the decision-maker the wherewithal to quantitatively assess the advantage of a superior (and presumably more expensive) sensor in light of the associated improvement in performance.

Appendix

Stochastic order and the ordering of sensors by sensitivity

For any random variable Θ, let F _Θ denote the cumulative distribution function, and let F _Θ ⁻¹ denote the quantile function; of course, if F _Θ is injective then F _Θ ⁻¹ is the inverse function of F _Θ, otherwise, for all u∈(0,1), recall that F _Θ ⁻¹(u)≔inf{w∈ℝ:F _Θ(w)⩾u}. (So, for example, F ⁻¹(0.25), F ⁻¹(0.5), and F ⁻¹(0.75) are the first quartile, median, and third quartile of the distribution, that is, the probability of being less than or equal to these numbers is 0.25, 0.5, and 0.75, respectively.) The random variable Θ₁ is said to be stochastically greater than or equal to the random variable Θ₂, denoted Θ₁⩾ _sto Θ₂, if for all w∈ℝ; straightforward computation confirms that this condition is equivalent to the condition that for all u∈(0,1).

Thus, in the notation from this paper, when we say that sensor (F _T ,F _N ) is at least as sensitive as sensor (F _T′,F _N′) precisely when F _T ⩾ _sto F _T′ and F _N′⩾ _sto F _N , what is meant is that, conditioning on an edge being traversable, each quantile for the marks generated by the at-least-as-sensitive-sensor (random vector ) is greater than or equal to that same quantile for the marks generated by the other sensor and, conditioning on an edge not being traversable, each quantile for the marks generated by the at-least-as-sensitive-sensor is less than or equal to that same quantile for the marks generated by the other sensor. So, very informally, if an edge is actually traversable then a more sensitive sensor can be more optimistic about the edge's traversability than the less sensitive sensor, and if an edge is actually nontraversable then the more sensitive sensor can be more pessimistic about the edge's traversability than the less sensitive sensor.

Also note that Θ₁⩾ _sto Θ₂ if and only if it holds that, for all nondecreasing real functions g, E[g(Θ₁)]⩾E[g(Θ₂)]. Thus, in the notation of this paper, if a protocol is strongly monotone then it is weakly monotone, but the converse does not necessarily hold.