Problem 568011 · easy · Robotics · Level 05 Planning and Mapping

Is That Tile a Chair Leg?

log-odds · Bayes' rule · inverse sensor model · clamping

A café robot maps the floor between the tables. For one floor cell it keeps a single number: the log-odds that the cell is occupied,

\ell = \log\frac{p}{1 - p}, \qquad p = 1 - \frac{1}{1 + e^{\ell}},

where p is the probability that the cell is occupied (math.log is the natural logarithm). Log-odds turn Bayes' rule for repeated readings into additions.

Before any reading the cell has the prior probability p0, so \ell starts at \ell_0 = \log\frac{p_0}{1 - p_0}. Each reading is 'H' (a laser echo came from this cell) or 'M' (a beam passed through it). The sensor model says how likely the cell is to be occupied given one reading on its own: p_hit after an 'H', p_miss after an 'M'. A reading changes the log-odds by its evidence minus the prior, and the result is then clamped into [l_min, l_max]:

\ell \leftarrow \min\Big(l_{\max},\ \max\Big(l_{\min},\ \ell + \log\frac{p_z}{1 - p_z} - \ell_0\Big)\Big)

with p_z = p_hit or p_miss.

Write cell_evidence(p0, readings, p_hit, p_miss, l_min, l_max), where readings is a string of 'H' and 'M', that returns the list of probabilities p after each reading, in order.

Examples

Input:  p0 = 0.5, readings = "HHM", p_hit = 0.7, p_miss = 0.4, l_min = -2, l_max = 2
Output: [0.7, 0.8448275862068966, 0.784]
Explanation: with p0 = 0.5 the prior's log-odds are 0. Each 'H' adds log(0.7/0.3) = 0.847,
the 'M' adds log(0.4/0.6) = -0.405: l = 0.847, 1.695, 1.289.

Input:  p0 = 0.5, readings = "HHHHM", p_hit = 0.9, p_miss = 0.3, l_min = -3, l_max = 3
Output: [0.9, 0.9525741268224333, 0.9525741268224333, 0.9525741268224333, 0.8959210117800368]
Explanation: two hits would make l = 4.39; it stops at 3. The miss then takes it to 2.153.

Input:  p0 = 0.2, readings = "HMH", p_hit = 0.6, p_miss = 0.1, l_min = -4, l_max = 4
Output: [0.6, 0.3999999999999999, 0.7999999999999999]
Explanation: l0 = log(0.25) = -1.386. Each hit adds 0.405 - (-1.386) = 1.792, the miss -2.197 + 1.386 = -0.811.

Constraints

  • l_min \le \ell_0 \le l_max
  • answers are compared with a tolerance of 1e-6; do not round

Goals

  • Turn probabilities into log-odds and back
  • Add the evidence of each reading to a cell's log-odds, minus the prior
  • Clamp the log-odds so the cell can still change its mind
Starting Python…