Scheduling an autonomous robot searching for hidden targets

Abstract

The problem of searching for hidden or missing objects (called targets) by autonomous intelligent robots in an unknown environment arises in many applications, e.g., searching for and rescuing lost people after disasters in high-rise buildings, searching for fire sources and hazardous materials, etc. Until the target is found, it may cause loss or damage whose extent depends on the location of the target and the search duration. The problem is to efficiently schedule the robot’s moves so as to detect the target as soon as possible. The autonomous mobile robot has no operator on board, as it is guided and totally controlled by on-board sensors and computer programs. We construct a mathematical model for the search process in an uncertain environment and provide a new fast algorithm for scheduling the activities of the robot which is used before an emergency evacuation of people after a disaster.

Appendices

Appendix 1. Proof of Claim 1

Let us introduce the following additional notation:

Event B_i = {after a single inspection, the AMR’s sensors declare that location i contains the target}.

Event C_i = {location i indeed contains the target}.

In terms of these events, the location probabilities p_i and the probabilities of the two types of error are expressed as follows:

$$ p_{i} = P\left( {C_{i} } \right);\quad \alpha_{i} = P\left( {B_{i} /\bar{C}_{i} } \right); \quad \beta_{i} = P\left( {\bar{B}_{i} /C_{i} } \right). $$

The probability f_i that the sensor declares that location i is detected as containing the target is

$$ f_{i} = P\left( {B_{i} } \right) = P\left( {B_{i} /C_{i} } \right)P\left( {C_{i} } \right) + P(B_{i} /\bar{C}_{i} )P\left( {\bar{C}_{i} } \right) = \left( {1 - \, \beta_{i} } \right)p_{i} + \, \alpha_{i} \left( {1 - p_{i} } \right). $$

The conditional probability of the event that location i contains the target under the condition that the sensor has declared that location i contains the target in a single inspection is

$$ P\left( {C_{i} /B_{i} } \right) = \frac{{P\left( {C_{i} } \right)P\left( {B_{i} /C_{i} } \right)}}{{P\left( {C_{i} } \right)P\left( {B_{i} /C_{i} } \right) + P\left( {\bar{C}_{i} } \right)P\left( {B_{i} /\bar{C}_{i} } \right)}} = \frac{{p_{i} \cdot \left( {1 - \beta_{i} } \right)}}{{p_{i} \cdot \left( {1 - \beta_{i} } \right) + \left( {1 - p_{i} } \right)\alpha_{i} }}. $$

We need to prove that the conditional probability $a_{{\left[ {i,h_{i} } \right]}}$ of the event that location i indeed contains the target under the condition that the sensor has declared in exactly h_i steps of the sequence s that location i contains the target satisfies the following relation:

$$ a_{{\left[ {i,h_{i} } \right]}} = P\left( {C_{i} /B_{i}^{\left( 1 \right)} \cap B_{i}^{\left( 2 \right)} \cap \cdots \cap B_{i}^{{\left( {h_{i} } \right)}} } \right) = \frac{{p_{i} \cdot \left( {1 - \beta_{i} } \right)^{{h_{i} }} }}{{p_{i} \cdot \left( {1 - \beta_{i} } \right)^{{h_{i} }} + \left( {1 - p_{i} } \right)\alpha_{i}^{{h_{i} }} }}. $$

Since the sequential inspections of locations made by the robot are independent, for any pair of indices i, j $\in$ {1,2,…,N}, we have the following equalities:

$$ \left\{ \begin{aligned} P\left( {B_{i}^{{\left( {k + 1} \right)}} /C_{i} \cap B_{j}^{\left( k \right)} } \right) = P\left( {B_{i}^{{\left( {k + 1} \right)}} /C_{i} } \right) \hfill \\ P\left( {B_{i}^{{\left( {k + 1} \right)}} /\bar{C}_{i} \cap B_{j}^{\left( k \right)} } \right) = P\left( {B_{i}^{{\left( {k + 1} \right)}} /\bar{C}_{i} } \right) \hfill \\ \end{aligned} \right.. $$

Therefore, $a_{{\left[ {i,h_{i} } \right]}} = \frac{{P\left( {C_{i} } \right) \cdot P\left( {B_{i}^{\left( 1 \right)} \cap B_{i}^{\left( 2 \right)} \cap \cdots \cap B_{i}^{{\left( {h_{i} } \right)}} /C_{i} } \right)}}{{P\left( {B_{i}^{\left( 1 \right)} \cap B_{i}^{\left( 2 \right)} \cap \cdots \cap B_{i}^{{\left( {h_{i} } \right)}} } \right)}} = \frac{{P\left( {C_{i} } \right)\, \cdot P^{{h_{i} }} \left( {B_{i}^{\left( 1 \right)} /C_{i} } \right)}}{{P\left( {C_{i} } \right)\, \cdot P^{{h_{i} }} \left( {B_{i}^{\left( 1 \right)} /C_{i} } \right) + P\left( {\bar{C}_{i} } \right)\, \cdot P^{{h_{i} }} \left( {B_{i}^{\left( 1 \right)} /\bar{C}_{i} } \right)}} = \frac{{p_{i} \cdot \left( {1 - \beta_{i} } \right)^{{h_{i} }} }}{{p_{i} \cdot \left( {1 - \beta_{i} } \right)^{{h_{i} }} + \left( {1 - p_{i} } \right)\alpha_{i}^{{h_{i} }} }}{.}$

The second part of the Claim 1 is proved along the same line.

Appendix 2. Proof of the Theorem

$$ s_{1} = U_{{\left[ {s_{1} ,0} \right]}} ,s_{1} \left[ 1 \right],s_{1} \left[ 2 \right], \ldots ,s_{1} \left[ n \right],s_{1} \left[ {n + 1} \right], \ldots $$

$$ s_{2} = U_{{\left[ {s_{1} ,0} \right]}} ,s_{1} \left[ 1 \right],s_{1} \left[ 2 \right], \ldots ,s_{1} \left[ {n + 1} \right],s_{1} \left[ n \right], \ldots $$

To prove the theorem, it suffices to prove the following relation:

$$ F\left( {s_{1} } \right) \le F\left( {s_{2} } \right) \Leftrightarrow Q_{{s_{1} \left[ n \right]}} \ge Q_{{s_{1} \left[ {n + 1} \right]}} . $$

We have:

$$ \begin{aligned} F\left( {s_{1} } \right) & = \sum\limits_{1 \le m \le M} {c_{{s_{1} \left[ m \right]}} \cdot T_{{s_{1} \left[ m \right]}} \cdot P_{{s_{1} \left[ m \right]}} } = \sum\limits_{1 \le m \le M} {c_{{s_{1} \left[ m \right]}} \cdot T_{{s_{1} \left[ m \right]}} \cdot P_{{s_{1} \left[ m \right]}} } \left( {A_{{s_{1} \left[ m \right]}} } \right) \\ & = \sum\limits_{m = 1}^{n - 1} {c_{{s_{1} \left[ m \right]}} \cdot T_{{s_{1} \left[ m \right]}} \cdot P_{{s_{1} \left[ m \right]}} } + \sum\limits_{n + 2 \le m \le M} {c_{{s_{1} \left[ m \right]}} \cdot T_{{s_{1} \left[ m \right]}} \cdot P_{{s_{1} \left[ m \right]}} } \\ & \quad + c_{{s_{1} \left[ n \right]}} \cdot T_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} + c_{{s_{1} \left[ {n + 1} \right]}} \cdot T_{{s_{1} \left[ {n + 1} \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} \\ \end{aligned} $$

$$ \begin{aligned} F\left( {s_{2} } \right) & = \sum\limits_{1 \le m \le M} {c_{{s_{2} \left[ m \right]}} \cdot T_{{s_{2} \left[ m \right]}} \cdot P_{{s_{2} \left[ m \right]}} } = \sum\limits_{1 \le m \le M} {c_{{s_{2} \left[ m \right]}} \cdot T_{{s_{2} \left[ m \right]}} \cdot P_{{s_{2} \left[ m \right]}} } \left( {A_{{s_{2} \left[ m \right]}} } \right) \\ & = \sum\limits_{m = 1}^{n - 1} {c_{{s_{2} \left[ m \right]}} \cdot T_{{s_{2} \left[ m \right]}} \cdot P_{{s_{2} \left[ m \right]}} } + \sum\limits_{n + 2 \le m \le M} {c_{{s_{2} \left[ m \right]}} \cdot T_{{s_{2} \left[ m \right]}} \cdot P_{{s_{2} \left[ m \right]}} } \\ & \quad + c_{{s_{2} \left[ n \right]}} \cdot T_{{s_{2} \left[ n \right]}} \cdot P_{{s_{2} \left[ n \right]}} + c_{{s_{2} \left[ {n + 1} \right]}} \cdot T_{{s_{2} \left[ {n + 1} \right]}} \cdot P_{{s_{2} \left[ {n + 1} \right]}} \\ \end{aligned} $$

$$ F\left( {s_{2} } \right) = \sum\limits_{m = 1}^{n - 1} {c_{{s_{1} \left[ m \right]}} \cdot T_{{s_{1} \left[ m \right]}} \cdot P_{{s_{1} \left[ m \right]}} } + \sum\limits_{n + 2 \le m \le M} {c_{{s_{1} \left[ m \right]}} \cdot T_{{s_{1} \left[ m \right]}} \cdot P_{{s_{1} \left[ m \right]}} } + c_{{s_{1} \left[ {n + 1} \right]}} \cdot \left( {T_{{s_{1} \left[ {n + 1} \right]}} - t_{{s_{1} \left[ n \right]}} } \right) \cdot P_{{s_{1} \left[ {n + 1} \right]}} + c_{{s_{1} \left[ n \right]}} \cdot T_{{s_{1} \left[ {n + 1} \right]}} \cdot P_{{s_{1} \left[ n \right]}} $$

$$ \begin{aligned} F\left( {s_{1} } \right) - F\left( {s_{2} } \right) & = c_{{s_{1} \left[ n \right]}} \cdot T_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} + c_{{s_{1} \left[ {n + 1} \right]}} \cdot T_{{s_{1} \left[ {n + 1} \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} \\ & \quad - c_{{s_{1} \left[ {n + 1} \right]}} \cdot \left( {T_{{s_{1} \left[ {n + 1} \right]}} - t_{{s_{1} \left[ n \right]}} } \right) \cdot P_{{s_{1} \left[ {n + 1} \right]}} - c_{{s_{1} \left[ n \right]}} \cdot T_{{s_{1} \left[ {n + 1} \right]}} \cdot P_{{s_{1} \left[ n \right]}} \\ & = - c_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} \cdot \left( {T_{{s_{1} \left[ {n + 1} \right]}} - T_{{s_{1} \left[ n \right]}} } \right) + c_{{s_{1} \left[ {n + 1} \right]}} \cdot t_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} \\ & = - c_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} \cdot t_{{s_{1} \left[ {n + 1} \right]}} + c_{{s_{1} \left[ {n + 1} \right]}} \cdot t_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} \\ \end{aligned} $$

We obtain that

$$ F\left( {s_{1} } \right) - F\left( {s_{2} } \right) = - c_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} \cdot t_{{s_{1} \left[ {n + 1} \right]}} + c_{{s_{1} \left[ {n + 1} \right]}} \cdot t_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} $$

$$ F\left( {s_{1} } \right) \le F\left( {s_{2} } \right) \Leftrightarrow F\left( {s_{1} } \right) - F\left( {s_{2} } \right) \le 0 \Leftrightarrow $$

$$ \begin{aligned} - c_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} \cdot t_{{s_{1} \left[ {n + 1} \right]}} + c_{{s_{1} \left[ {n + 1} \right]}} \cdot t_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} \le 0 \Leftrightarrow \hfill \\ c_{{s_{1} \left[ {n + 1} \right]}} \cdot t_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} \le c_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} \cdot t_{{s_{1} \left[ {n + 1} \right]}} \Leftrightarrow \hfill \\ \frac{{c_{{s_{1} \left[ {n + 1} \right]}} \cdot P_{{s_{1} \left[ {n + 1} \right]}} }}{{t_{{s_{1} \left[ {n + 1} \right]}} }} \le \frac{{c_{{s_{1} \left[ n \right]}} \cdot P_{{s_{1} \left[ n \right]}} }}{{t_{{s_{1} \left[ n \right]}} }} \Leftrightarrow \hfill \\ Q_{{s_{1} \left[ {n + 1} \right]}} \le Q_{{s_{1} \left[ n \right]}} \Leftrightarrow \hfill \\ Q_{{s_{1} \left[ n \right]}} \ge Q_{{s_{1} \left[ {n + 1} \right]}} \hfill \\ \end{aligned} $$

The theorem is proved.