Motion planning for robot audition

Abstract

Robot audition refers to a range of hearing capabilities which help robots explore and understand their environment. Among them, sound source localization is the problem of estimating the location of a sound source given measurements of its angle of arrival with respect to a microphone array mounted on the robot. In addition, robot motion can help quickly solve the front-back ambiguity existing in a linear microphone array. In this article, we focus on the problem of exploiting robot motion to improve the estimation of the location of an intermittent and possibly moving source in a noisy and reverberant environment. We first propose a robust extended mixture Kalman filtering framework for jointly estimating the source location and its activity over time. Building on this framework, we then propose a long-term robot motion planning algorithm based on Monte Carlo tree search to find an optimal robot trajectory according to two alternative criteria: the Shannon entropy or the standard deviation of the estimated belief on the source location. These criteria are integrated over time using a discount factor. Experimental results show the robustness of the proposed estimation framework to false angle of arrival measurements within $\pm \,20^{\circ }$ and 10% false source activity detection rate. The proposed robot motion planning technique achieves an average localization error 48.7% smaller than a one-step-ahead method. In addition, we compare the correlation between the estimation error and the two criteria, and investigate the effect of the discount factor on the performance of the proposed motion planning algorithm.

Chernoff–Hoeffding inequality

The UCT criterion derives from the Chernoff-Hoeffding inequality which is valid for a bounded reward function (Hoeffding 1963). The Chernoff-Hoeffding inequality is stated in the theorem below.

Theorem: Let $Y_1, Y_2, \ldots , Y_n$ be independent random variables whose values are within the range [a, b]. Denote $\mu _i = {\mathbb {E}}(Y_i)$ as their expected values, $Y = \frac{1}{n}\sum _iY_i$ and $\mu ={\mathbb {E}}(Y)=\frac{1}{n}\sum _i\mu _i$. Then for all $\epsilon >0$, we have:

$$\begin{aligned} P(|Y-\mu |>\epsilon )\le 2e^{-2n\epsilon ^2/(b-a)^2}. \end{aligned}$$

(41)

For us, $Y_i$ is the reward Q at the end of each simulation and Y is the average reward $\frac{{\bar{Q}}(n')}{N(n')}$ at each child node in the tree. So, to satisfy the Chernoff-Hoeffding inequality, the two criteria: entropy and standard deviation must be bounded. We show that these two criteria are bounded in the following subsections.

1.1 Bounded entropy

For a scalar random variable X in the range [a, b] with no other constraints, the maximum entropy distribution of X is the uniform distribution over this range. In that case the formula for calculating the maximum entropy is expressed as follows:

$$\begin{aligned} \begin{aligned} H_{\mathrm {max,X}}&= -\int ^b_a{p(X)\log {p(X)}}dX \\&= -\log {p(X)}\int ^b_a{p(X)}dX \\&= -\log {p(X)} \\&= -\log {\frac{1}{(b-a)}} \\&= \log (b-a) \\&= \log \left| \mathrm {range}_{X}\right| \end{aligned} \end{aligned}$$

(42)

The formula for computing the maximum entropy of the belief is:

$$\begin{aligned} \begin{aligned} H_{\mathrm {max}}&=\log {\left| \mathrm {range}_{x_{\mathrm {r}}}\right| } + \log {\left| \mathrm {range}_{y_{\mathrm {r}}}\right| } +\log {\left| \mathrm {range}_{\theta _{\mathrm {r}}}\right| } \\&\quad +\log {\left| \mathrm {range}_{x_{\mathrm {s}}}\right| } +\log {\left| \mathrm {range}_{y_{\mathrm {s}}}\right| }+ \log {\left| \mathrm {range}_{\theta _{\mathrm {s}}}\right| } \\&\quad +\log {\left| \mathrm {range}_{v_{\mathrm {s}}}\right| }+\log {\left| \mathrm {range}_{w_{\mathrm {s}}}\right| } \\&=20.3027. \end{aligned} \end{aligned}$$

(43)

In theory, the minimum entropy with perfect knowledge is $-\infty$ but it is not achievable in practice. So the lower bound can be computed as follows. In order to find the minimum entropy of the estimated belief, we begin the belief propagation with perfect knowledge about the source position. In the nonlinear MKF, it is represented by one hypothesis of active source whose variance for the source position is equal to 0. After the prediction step, there will be one hypothesis of active source with a higher weight and one hypothesis of inactive source with a lower weight. The uncertainty will appear due to the process noise Q in the dynamic model. We then evaluate the uncertainty of estimation of the source location after the update step. We find the angle from the robot to the source, the distance from the robot to the source in the range from 0.18 m to 8 m, and the AoA observation such that the entropy of the belief after the update step above is minimum. As a result, the minimum entropy $H_{\mathrm {min}}$ is $-38.7824$ obtained for an AoA of $176^{\circ }$, which does not suffer from the front-back ambiguity, and a distance of 0.18 m from the robot to the source.

So, the entropy is bounded upwards by the entropy of the uniform distribution on the state vector, and downwards by the entropy of the probability distribution in the case when there is no front-back ambiguity and the sound source is as close as possible to the robot (0.18 m due to the size of the robot).

1.2 Bounded standard deviation

Let a and b be respectively the lower and upper bounds on the values of any random variable with a particular probability distribution. Then, according to Popoviciu’s inequality on variances (Popoviciu 1935), its variance satisfies:

$$\begin{aligned} {\sigma ^2}\le {\frac{1}{4}}(b-a)^{2}, \end{aligned}$$

(44)

or its standard deviation is bounded as follows:

$$\begin{aligned} -{\frac{1}{2}}(b-a)\le {\sigma }\le {\frac{1}{2}}(b-a). \end{aligned}$$

(45)