Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Aided Optimal Search: Data-Driven Target Pursuit from On-Demand Delayed Binary Observations

  • Chapter
  • First Online:
Handbook of Dynamic Data Driven Applications Systems

Abstract

We consider the following search problem: an autonomous robot (the searcher) needs to locate and reach a target moving in a field scattered with Unattended Ground Sensors (UGS). The searcher has very limited information about the target: (i) it has an initial distribution (the prior) describing the probability of the target being at a given location at the initial time, and (ii) it can interrogate nearby sensors; each sensor records a binary measurement, describing whether or not the target passed in the proximity of the sensor at some point in time. Then the goal for the searcher is to estimate the trajectory of the target, and plan a maneuver that allows reducing the uncertainty about the current target state. We refer to this problem as aided optimal search, in that the search process is aided by an external infrastructure (the ground sensors). The paper adopts a Dynamic Data-Driven Appplications Systems (DDDAS) paradigm, in which the data collected by the searcher is used to update the belief on the trajectory of the target, and the searcher actively steers the measurement process to improve its knowledge about the location of the target. In particular, we make two main contributions. The first regards the target trajectory estimation. We show how to perform optimal Bayesian inference from binary measurements using a Gaussian Mixture Model (GMM). One of the main insights is that parameterizing the GMM in the information filter (inverse covariance) form allows huge computational savings: the information matrix of each mixture component is a very sparse (block-tridiagonal) matrix, which allows us to deal with a GMM with thousands of components in a fraction of a second. The second contribution regards planning: we propose a Mixed-Integer Programming (MIP) approach to plan the optimal searcher path, which minimizes the uncertainty about the position of the target. The key idea here is the use of sampling to decouple the complexity of the MIP from the length of the trajectory of the target. We demonstrate the proposed strategy in extensive simulations, reporting statistics about success rate and computational time for different scenarios and target motion models. The proposed search strategy largely outperforms greedy strategies (e.g., visiting the most likely target position).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 189.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In practice, the most challenging part of the problem is indeed the initial phase of the search in which the uncertainty about the target is large and most of the interrogated sensors are far from the actual trajectory of the target.

  2. 2.

    When b iτ = 1, the weight update is \(v^{(k)}_{\tau +1} = v^{(k)}_{\tau } + \log p^{(k)}_{i\tau } \leq v^{(k)}_{\tau }\) (recall: \(p^{(k)}_{i\tau } \leq 1\) hence \(\log p^{(k)}_{i\tau }\) is negative), leading to a smaller objective.

  3. 3.

    Think about the extreme case in which the target and the searcher have the same speed: then if the target moves in the opposite direction with respect to the searcher position, no search strategy can make the searcher reach the target before it escapes the region \(\mathcal {R}\).

References

  1. M. Adler, H. Räcke, N. Sivadasan, C. Sohler, B. Vöcking, Randomized pursuit-evasion in graphs. Comb. Probab. Comput. 12(3), 225–244, (2003)

    Article  MathSciNet  Google Scholar 

  2. N. Ahmed, D. Casbeer, Y. Cao, D. Kingston, Bayesian hidden markov models for UAV-enabled target localization on road networks with soft-hard data. in SPIE Defense and Security Symposium, 2015

    Google Scholar 

  3. M. Aigner, M. Fromme, A game of cops and robbers. Discret. Appl. Math. 8(1), 1–12 (1984)

    Article  MathSciNet  Google Scholar 

  4. G. Allen, Building a dynamic data driven application system for hurricane forecasting, in Computational Science – ICCS 2007 (Springer, Berlin/Heidelberg, 2007), pp. 1034–1041

    Google Scholar 

  5. L. Alonso, A.S. Goldstein, E.M. Reingold, Lion and man: upper and lower bounds. INFORMS J. Comput. 4(4), 447–452 (1992)

    Article  MathSciNet  Google Scholar 

  6. D. Alspach, H. Sorenson, Nonlinear bayesian estimation using gaussian sum approximations. IEEE Trans. Autom. Control 17(4), 439–448 (1972)

    Article  Google Scholar 

  7. D. Assaf, S. Zamir, Optimal sequential search: a bayesian approach. Ann. Stat. 13(3), 1213–1221 (1985)

    Article  MathSciNet  Google Scholar 

  8. H. Bai, H. David, W.S. Lee, Integrated perception and planning in the continuous space: a POMDP approach, in Robotics: Science and Systems (RSS), 2013

    Google Scholar 

  9. T. Basar, G.J. Olsder, Dynamic Noncooperative Game Theory. Classics in Applied Mathematics, 2nd edn. (SIAM, Philadelphia, 1999)

    Google Scholar 

  10. E. Blasch, P. Maupin, A. Jousselme, Sensor-based allocation for path planning and area coverage using ugss, in IEEE National Aerospace and Electronics Conference (NAECON), 2010, pp. 361–368

    Google Scholar 

  11. E. Blasch, J. Dezert, P. Valin, DSmt applied to seismic and acoustic sensor fusion, in IEEE National Aerospace and Electronics Conference (NAECON), 2011, pp. 79–86

    Google Scholar 

  12. E.P. Blasch, K. Pham, D. Shen, Chen G, Orbital satellite pursuit-evasion game-theoretical control, in IEEE International Conference on Information Science, Signal Processing and Application (ISSPA), 2012

    Google Scholar 

  13. A. Blum, M.L. Furst, Approximation algorithms for orienteering and discounted-reward TSP, in Symposium on Foundations of Computer Science, 2003, pp. 46–55

    Google Scholar 

  14. S.D. Bopardikar, F. Bullo, J.P. Hespanha, Sensing limitations in the lion and man problem, in American Control Conference, 2007, pp. 5958–5963

    Google Scholar 

  15. F. Bourgault, T. Furukawa, H.F. Durrant-Whyte, Coordinated decentralized search for a lost target in a Bayesian world, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2003, pp. 48–53

    Google Scholar 

  16. F. Bourgault, T. Furukawa, H.F. Durrant-Whyte, Optimal search for a lost target in a Bayesian world, in International Conference on Field and Service Robotics, Springer Tracts in Advanced Robotics (STAR), 2006, pp. 209–222

    Google Scholar 

  17. D. Casbeer, K Meier, Y Cao, Estimating the state of an intruder with a UAV and unattended ground sensors, in AIAA Infotech Aerospace Conference, 2013, pp. 4269–4275

    Google Scholar 

  18. D. Casbeer, K. Krishnamoorthy, P. Chandler, M. Pachter, Moving ground target isolation by a UAV using predicted observations, in IEEE Conference on Decision and Control, 2014, pp. 4284–4289

    Google Scholar 

  19. C. Chekuri, N. Korula, M. Pál, Improved algorithms for orienteering and related problems. ACM Trans. Algorithms 8(3), 1–27 (2012)

    Article  MathSciNet  Google Scholar 

  20. H. Chen, K. Krishnamoorthy, W. Zhang, D. Casbeer, Continuous-time intruder isolation using unattended ground sensors on graphs, in American Control Conference, 2014, pp. 5270–5275

    Google Scholar 

  21. H. Chen, K. Krishnamoorthy, W. Zhang, D. Casbeer, Intruder isolation on a general road network under partial information. IEEE Trans. Control Syst. Technol. 25(1), 222–234 (2017)

    Article  Google Scholar 

  22. H.L. Choi, J.P. How, J.A. Hansen, Ensemble-based adaptive targeting of mobile sensor networks, in 2007 American Control Conference, 2007, pp. 2393–2398

    Google Scholar 

  23. H.L. Choi, J.P. How, Efficient targeting of sensor networks for large-scale systems. IEEE Trans. Control Syst. Technol. 19(6), 1569–1577 (2011)

    Article  Google Scholar 

  24. C.-Y. Chong, S.P. Kumar, Sensor networks: evolution, opportunities, and challenges, in Proceedings of the IEEE, 2003, pp. 1247–1256

    Google Scholar 

  25. T. Chung, G. Hollinger, V. Isler, Search and pursuit-evasion in mobile robotics: a survey. Auton. Robot. 31(4), 299–316 (2011)

    Article  Google Scholar 

  26. D. Crouse, P. Willett, K. Pattipati, L. Svensson, A look at gaussian mixture reduction algorithms, in 14th International Conference on Information Fusion, 2011, pp. 1–8

    Google Scholar 

  27. F. Darema, Dynamic data driven applications systems: a new paradigm for application simulations and measurements, in Computational Science – ICCS 2004: 4th International Conference, Krakow, Poland, 6–9 June 2004, Proceedings, Part III, eds. M. Bubak, G.D. van Albada, P.M.A. Sloot, J.J. Dongarra. Lecture Notes in Computer Science, vol. 3038 (Springer, Heidelberg, 2004), pp. 662–669

    Google Scholar 

  28. F. Darema, Grid computing and beyond: the context of dynamic data driven applications systems. Proc. IEEE 93(3), 692–697 (2005)

    Article  Google Scholar 

  29. C.C. Douglas, M.J. Cole, P. Dostert, Y. Efendiev, R.E. Ewing, G. Haase, J. Hatcher, M. Iskandarani, C.R. Johnson, R.A. Lodder, Dynamically identifying and tracking contaminants in water bodies, in Computational Science – ICCS 2007: 7th International Conference, Beijing, 7th International Conference, 27–30 May 2007, Proceedings, Part I, eds. Y. Shi, G.D. van Albada, J.J. Dongarra, P.M.A. Sloot. Lecture Notes in Computer Science, vol. 4487 (Springer, Heidelberg, 2007), pp. 1002–1009

    Google Scholar 

  30. M.F. Duarte, Y.H. Hu, Vehicle classification in distributed sensor networks. J. Parallel Distrib. Comput. 64(7), 826–838 (2004)

    Article  Google Scholar 

  31. J.N. Eagle, The optimal search for a moving target when the search path is constrained. Oper. Res. 32, 1105–1115 (1984)

    Article  MathSciNet  Google Scholar 

  32. J.N. Eagle, J.R. Yee, An optimal branch-and-bound procedure for the constrained path, moving target search problem. Oper. Res. 32(1), 110–114 (1990)

    Article  MathSciNet  Google Scholar 

  33. T. Erez, W.D. Smart, A scalable method for solving high-dimensional continuous POMDPs using local approximation, in Conference in Uncertainty in Artificial Intelligence (UAI), 2010

    Google Scholar 

  34. R. Fujimoto, A. Guin, M. Hunter, H. Park, R. Kannan, G. Kanitkar, M. Milholen, S. Neal, P. Pecher, A dynamic data driven application system for vehicle tracking. Proc. Comput. Sci. 29, 1203–1215 (2014)

    Article  Google Scholar 

  35. L. Guibas, J. Latombe, S. LaValle, D. Lin, R. Motwani, Visibility-based pursuit-evasion in a polygonal environment. Int. J. Comput. Geom. Appl. 9(5), 471–494 (1999)

    Article  Google Scholar 

  36. T. Hastie, R. Tibshirani, J.H. Friedman, The Elements of Statistical Learning (Springer, New York, 2001)

    Book  Google Scholar 

  37. G. Hollinger, G. Sukhatme, Stochastic motion planning for robotic information gathering, in Robotics: Science and Systems (RSS), 2013

    Google Scholar 

  38. G. Hollinger, S. Singh, J. Djugash, A. Kehagias, Efficient multi-robot search for a moving target. Int. J. Robot. Res. 28(2), 201–219 (2009)

    Article  Google Scholar 

  39. V. Indelman, L. Carlone, F. Dellaert, Planning in the continuous domain: a generalized belief space approach for autonomous navigation in unknown environments. Int. J. Robot. Res. 34(7), 849–882 (2015)

    Article  Google Scholar 

  40. V. Isler, S. Kannan, S. Khanna, Randomized pursuit-evasion with local visibility. SIAM J. Discret. Math. 1(20), 26–41 (2006)

    Article  MathSciNet  Google Scholar 

  41. V. Isler, N. Karnad, The role of information in the cop-robber game. Theor. Comput. Sci. Spec. Issue Graph Search. 3(399), 179–190 (2008)

    Article  MathSciNet  Google Scholar 

  42. R. Ivanov, N. Atanasov, M. Pajic, G. Pappas, I. Lee, Robust estimation using context-aware filtering, in Allerton Conference on Communication, Control, and Computing, 2015

    Google Scholar 

  43. B. Jia, K.D. Pham, E. Blasch, D. Shen, Z. Wang, G. Chen, Cooperative space object tracking using space-based optical sensors via consensus-based filters. IEEE Trans. Aerosp. Electron. Syst. 52(3), 1908–1936 (2016)

    Article  Google Scholar 

  44. S. Joshi, S. Boyd, Sensor selection via convex optimization. IEEE Trans. Signal Process. 57, 451–462 (2009)

    Article  MathSciNet  Google Scholar 

  45. J. Kadane, Optimal whereabouts search. Oper. Res. 19(4), 894–904 (1971)

    Article  MathSciNet  Google Scholar 

  46. L.P. Kaelbling, M.L. Littman, A.R. Cassandra, Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1), 99–134 (1998)

    Article  MathSciNet  Google Scholar 

  47. S. Karaman, E. Frazzoli, Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)

    Article  Google Scholar 

  48. B.O. Koopman, The theory of search. Part III: the optimum distribution of searching effort. Oper. Res. 5(5), 613–626 (1957)

    Google Scholar 

  49. K. Krishnamoorthy, D. Casbeer, P. Chandler, M. Pachter, S. Darbha, UAV search & capture of a moving ground target under delayed information, in IEEE Conference on Decision and Control, 2012, pp. 3092–3097

    Google Scholar 

  50. K. Krishnamoorthy, S. Darbha, P.P. Khargonekar, D. Casbeer, P. Chandler, M. Pachter, Optimal minimax pursuit evasion on a manhattan grid, in IEEE Conference on Decision and Control, 2013, pp. 3421–3428

    Google Scholar 

  51. K. Krishnamoorthy, D. Casbeer, P. Chandler, M. Pachter, Pursuit on a graph using partial information, in American Control Conference, 2015, pp. 4269–4275

    Google Scholar 

  52. H. Lau, S. Huang, G. Dissanayake, Optimal search for multiple targets in a built environment, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2005, pp. 3740–3745

    Google Scholar 

  53. H. Lau, S. Huang, G. Dissanayake, Probabilistic search for a moving target in an indoor environment, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2006, pp. 3393–3398

    Google Scholar 

  54. J.J. Lim, H. Pirsiavash, A. Torralba, Parsing IKEA objects: fine pose estimation, in International Conference on Computer Vision (ICCV), 2013, pp. 2992–2999

    Google Scholar 

  55. J. Mandel, L.S. Bennethum, J.L. Coen M. Chen, C.C. Douglas, L.P. Franca, Towards a dynamic data driven application system for wildfire simulation, in Computational Science – ICCS 2005 (Springer, Berlin/Heidelberg, 2005)

    Google Scholar 

  56. R. Niu, P.K. Varshney, Target location estimation in sensor networks with quantized data. IEEE Trans. Signal Process. 54(12), 4519–4528 (2006)

    Article  Google Scholar 

  57. S.C.W. Ong, S.W. Png, D. Hsu, W.S. Lee, Planning under uncertainty for robotic tasks with mixed observability. Int. J. Robot. Res. 29(8), 1053–1068 (2010)

    Article  Google Scholar 

  58. R. Platt Jr., R. Tedrake, L.P. Kaelbling, T. Lozano-Pérez, Belief space planning assuming maximum likelihood observations, in Robotics: Science and Systems (RSS), 2010, pp. 587–593

    Google Scholar 

  59. S. Rasmussen, D. Kingston, Development and flight test of an area monitoring system using unmanned aerial vehicles and unattended ground sensors, in International Conference on Unmanned Aircraft Systems (ICUAS), 2015

    Google Scholar 

  60. N. Roy, G. Gordon, S. Thrun, Finding approximate POMDP solutions through belief compression. J. Artif. Intell. Res. 23, 1–40 (2005)

    Article  Google Scholar 

  61. A.R. Runnalls, Kullback-Leibler approach to gaussian mixture reduction. IEEE Trans. Aerosp. Electron. Syst. 43(3), 989–999 (2007)

    Article  Google Scholar 

  62. H. Sato, J.O. Royset, Path optimization for the resource-constrained searcher. Nav. Res. Logist. 57(5), 422–440 (2010)

    MathSciNet  MATH  Google Scholar 

  63. D. Shen, G. Chen, H. Ling, K.D. Pham, E. Blasch, Methods and devices for demonstrating three-player pursuit-evasion game. U.S. Patent application Publication 2016/0121204 A1, 5 May 2016

    Google Scholar 

  64. D. Silver, J. Veness, Monte-Carlo planning in large POMDPs, in Advances in Neural Information Processing Systems (NIPS), 2010, pp. 2164–2172

    Google Scholar 

  65. H.W. Sorenson, D.L. Alspach, Recursive bayesian estimation using gaussian sums. Automatica 7, 465–479 (1971)

    Article  MathSciNet  Google Scholar 

  66. C. Stachniss, G. Grisetti, W. Burgard, Recovering particle diversity in a Rao-Blackwellized particle filter for SLAM after actively closing loops, in IEEE International Conference on Robotics and Automation (ICRA), 2005, pp. 667–672

    Google Scholar 

  67. L.D. Stone. Theory of Optimal Search, 2nd edn. (Academic, San Diego, 1989)

    Google Scholar 

  68. S. Thrun, W. Burgard, D. Fox, Probabilistic Robotics (The MIT Press, Cambridge, 2005)

    MATH  Google Scholar 

  69. K.E. Trummel, J.R. Weisinger, The complexity of the optimal searcher path problem. Oper. Res. 34(2), 324–327 (1986)

    Article  MathSciNet  Google Scholar 

  70. J. Van Den Berg, S. Patil, R. Alterovitz, Motion planning under uncertainty using iterative local optimization in belief space. Int. J. Robot. Res. 31(11), 1263–1278 (2012)

    Article  Google Scholar 

  71. P. Vansteenwegen, W. Souffriau, D.V. Oudheusden, The orienteering problem: a survey. Eur. J. Oper. Res. 209, 1–10 (2011)

    Article  MathSciNet  Google Scholar 

  72. A.R. Washburn, Search for a moving target: the FAB algorithm. Oper. Res. 31(4), 739–751 (1983)

    Article  Google Scholar 

  73. J. Yu, J. Aslam, S. Karaman, D. Rus, Optimal tourist problem and anytime planning of trip itineraries. arXiv: 1409.8536 (2015)

    Google Scholar 

  74. B. Zhang, C. Zhang, Finite mixture models with negative components, in International Conference on Machine Learning and Data Mining in Pattern Recognition, 2005, pp. 31–41

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Massachusetts Institute of Technology, Cambridge, MA, USA

    Luca Carlone & Sertac Karaman

  2. Coordinated Science Lab, University of Illinois at Urbana-Champaign, Urbana, IL, USA

    Allan Axelrod & Girish Chowdhary

Authors
  1. Luca Carlone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Allan Axelrod
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sertac Karaman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Girish Chowdhary
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luca Carlone .

Editor information

Editors and Affiliations

  1. Air Force Office of Scientific Research, Air Force Research Laboratory, Arlington, VA, USA

    Erik Blasch

  2. Earth, Atmospheric and Planetary Sciences, Massachusetts Institute of Technology, Cambridge, MA, USA

    Sai Ravela

  3. Information Directorate, Air Force Research Laboratory, Rome, NY, USA

    Alex Aved

Prediction Equations

Prediction Equations

In this section we derive the equations for the prediction phase of our incremental smoother. We start with a lemma, which will be useful to simplify the derivation later on.

Lemma 1 (From measurement to state space)

Given a multivariate Gaussian \(\mathcal {N}(A x; \eta , \Omega )\) , with \(A \in { {\mathbb R}^{d \times d} } \) and full rank, then the multivariate Gaussian can be written equivalently as:

$$\displaystyle \begin{aligned} \mathcal{N}(A x; \eta, \Omega) = \mathcal{N}(x; A^{\mathsf{T}} \eta, A^{\mathsf{T}} \Omega A) \end{aligned} $$
(14.52)

Proof. We prove the claim by inspection. We write explicitly the right-hand side of (14.52) as:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} \mathcal{N}(x; A^{\mathsf{T}} \eta, A^{\mathsf{T}} \Omega A) = k \; \text{exp} \bigg\{ -\frac{1}{2} [ x - (A^{\mathsf{T}} \Omega A)^{-1} A^{\mathsf{T}} \eta ]^{\mathsf{T}} \times \\ \hspace{4cm} (A^{\mathsf{T}} \Omega A) [ x - (A^{\mathsf{T}} \Omega A)^{-1} A^{\mathsf{T}} \eta ] \bigg\} = \\ k \; \text{exp} \bigg\{ -\frac{1}{2} \bigg[ x^{\mathsf{T}} (A^{\mathsf{T}} \Omega A) x - 2 \eta^{\mathsf{T}} A x + \eta^{\mathsf{T}} A (A^{\mathsf{T}} \Omega A)^{-1} A^{\mathsf{T}} \eta \bigg] \bigg\} \end{array} \end{aligned} $$
(14.53)

From the fact that A is square and full rank (hence invertible), the previous simplifies to:

$$\displaystyle \begin{aligned} \begin{array}{lll} k \; \text{exp} \bigg\{ -\frac{1}{2} \bigg[ (A x)^{\mathsf{T}} \Omega (A x) - 2 \eta^{\mathsf{T}} A x + \eta^{\mathsf{T}} \Omega^{-1} \eta \bigg] \bigg\} = \\ k \; \text{exp} \bigg\{ -\frac{1}{2} \bigg[ (A x - \Omega^{-1}\eta)^{\mathsf{T}} \Omega (A x - \Omega^{-1}\eta) \bigg] \bigg\} = \mathcal{N}(A x; \eta, \Omega) \end{array} \end{aligned} $$
(14.54)

which proves the claim. □

We can now focus on the derivation of the prediction equations. Let us start from the general prediction Eq. (14.14):

$$\displaystyle \begin{aligned} {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) = {\mathbb P}\left(y_{t+1} | y_{t}\right) {\mathbb P}\left(y_{1:t} | Z_{1:t}\right) \end{aligned} $$
(14.55)

Substituting our choice of prior probability (14.15) and transition probability (14.7), we get:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) &=& \mathcal{N}(y_{t+1} - A y_t; 0,\Omega_w) \mathcal{M}(y_{1:t} ; \{\eta_{t,j}, \Omega_{t,j}, \alpha_{t,j} \}_{j=1}^m) = \\ && \mathcal{N}(y_{t+1} - A y_t; 0,\Omega_w) \sum_{j=1}^m \alpha_{t,j} \mathcal{N}(y_{1:t} \; ; \eta_{t,j}, \Omega_{t,j}) = \\ && \sum_{j=1}^m \alpha_{t,j} \mathcal{N}(y_{t+1} - A y_t; 0,\Omega_w) \mathcal{N}(y_{1:t} ; \eta_{t,j}, \Omega_{t,j}) \end{array}\end{aligned} $$
(14.56)

Now we use the definition of S 1:t and S t:t+1, given in (14.18), which we substitute in (14.56):

$$\displaystyle \begin{aligned} \begin{array}{lll} {} {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) = \sum_{j=1}^m \alpha_{t,j} \mathcal{N}(S_{t:t+1} y_{1:t+1}; 0,\Omega_w) \mathcal{N}(S_{1:t} y_{1:t+1} ; \eta_{t,j}, \Omega_{t,j}) \end{array} \end{aligned} $$
(14.57)

We can develop each summand as follows:

(14.58)

Noting that the matrix \(\left [\begin {array}{c} S_{1:t} \\ S_{t:t+1} \end {array}\right ]\) is square and full rank, we apply Lemma 1 and simplify the previous expression as:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} \mathcal{N}(S_{t:t+1} y_{1:t+1}; 0,\Omega_w) \mathcal{N}(S_{1:t} y_{1:t+1} ; \eta_{t,j}, \Omega_{t,j}) = \\ \mathcal{N}(y_{1:t+1} ; S_{1:t}^{\mathsf{T}} \eta_{t,j}, S_{1:t}^{\mathsf{T}} \Omega_{t,j} S_{1:t} + S_{t:t+1}^{\mathsf{T}} \Omega_{t,j} S_{t:t+1} ) \end{array} \end{aligned} $$
(14.59)

Substituting (14.59) back into (14.57), we obtain:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) = \sum_{j=1}^m \alpha_{t,j} \mathcal{N}(y_{1:t+1} ; S_{1:t}^{\mathsf{T}} \eta_{t,j}, S_{1:t}^{\mathsf{T}} \Omega_{t,j} S_{1:t} + S_{t:t+1}^{\mathsf{T}} \Omega_{t,j} S_{t:t+1} ) \end{array} \end{aligned} $$
(14.60)

which coincides with Eqs. (14.16) and (14.17).

1.1 B Update Equations

In this section we derive the equations for the update phase of our incremental smoother. We start with a lemma, which will be useful to simplify the derivation later on.

Lemma 2 (Update in Information Form)

Given two multivariate Gaussians \(\mathcal {N}(x; \bar {\eta }, \bar {\Omega })\) and \(\mathcal {N}(A x; \eta _a, \Omega _a)\) , with \(x \in { {\mathbb R}^{d} } \) and \(A \in { {\mathbb R}^{d_a \times d} } \) (full row rank, d a ≤ d), then the following equality holds:

$$\displaystyle \begin{aligned} \mathcal{N}(A x; \eta_a, \Omega_a) \mathcal{N}(x; \bar{\eta}, \bar{\Omega}) = \kappa \mathcal{N}(x; \bar{\eta} + A^{\mathsf{T}} \eta_a, \bar{\Omega} + A^{\mathsf{T}} \Omega_a A ) \end{aligned} $$
(14.61)

where κ is a constant independent on x.

Proof. We prove the claim by inspection. We write explicitly the left-hand side of (14.61) as:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} \mathcal{N}(A x; \eta_a, \Omega_a) \mathcal{N}(x; \bar{\eta}, \bar{\Omega}) = \frac{ \det(\bar{\Omega})^{\frac{1}{2}} }{ (2\pi)^{\frac{d}{2}} } \frac{ \det(\Omega_a)^{\frac{1}{2}} }{ (2\pi)^{\frac{d_a}{2}} } \times \\ \; \text{exp} \bigg\{ -\frac{1}{2} \bigg[ (Ax - \Omega_a^{-1} \eta_a)^{\mathsf{T}} \Omega_a (Ax - \Omega_a^{-1} \eta_a) + (x - \bar{\Omega}^{-1} \bar{\eta})^{\mathsf{T}} \bar{\Omega} (x - \bar{\Omega}^{-1} \bar{\eta}) \bigg] \bigg\} = \\ {\mbox{(developing the squares and introducing} {\kappa} \mbox{to denote constant factors)} } \\ \kappa \times \; \text{exp} \bigg\{ -\frac{1}{2} \bigg[ x^{\mathsf{T}} (\bar{\Omega} {+} A^{\mathsf{T}} \Omega_a A) x {-} 2 x^{\mathsf{T}} (\bar{\eta} {+} A^{\mathsf{T}} \eta_a) + \eta_a^{\mathsf{T}} \Omega_a^{-1} \eta_a + \bar{\eta}^{\mathsf{T}} \bar{\Omega}^{-1} \bar{\eta} \bigg] \bigg\} = \\ {\mbox{(including constants at the exponent in} {\kappa)} } \\ \kappa \times \; \text{exp} \bigg\{ -\frac{1}{2} \bigg[ x^{\mathsf{T}} (\bar{\Omega} + A^{\mathsf{T}} \Omega_a A) x - 2 x^{\mathsf{T}} (\bar{\eta} + A^{\mathsf{T}} \eta_a) \bigg] \bigg\} = \\ {\mbox{(reincluding more convenient constants at the exponent)} } \\ \kappa \times \text{exp} \bigg\{ -\frac{1}{2} \bigg[ x^{\mathsf{T}} (\bar{\Omega} + A^{\mathsf{T}} \Omega_a A) x - 2 x^{\mathsf{T}} (\bar{\eta} + A^{\mathsf{T}} \eta_a) + \\ (\bar{\eta} + A^{\mathsf{T}} \eta_a)^{\mathsf{T}} (\bar{\Omega} + A^{\mathsf{T}} \Omega_a A)^{-1} (\bar{\eta} + A^{\mathsf{T}} \eta_a) \bigg] \bigg\} = \\ {\text{(isolating}\ \text{the}\ \text{Gaussian}\ \text{term,}\ \text{up}\ \text{to}\ \text{constant)} } \\ \kappa \times \mathcal{N}(x; \bar{\eta} + A^{\mathsf{T}} \eta_a, \bar{\Omega} + A^{\mathsf{T}} \Omega_a A ) \end{array} \end{aligned} $$
(14.62)

A simple way to explicitly compute the constant κ is to observe that:

$$\displaystyle \begin{aligned} \begin{array}{rcl} \int \mathcal{N}(A x; \eta_a, \Omega_a) \mathcal{N}(x; \bar{\eta}, \bar{\Omega}) \text{d}x = \end{array} \end{aligned} $$
(14.63)
$$\displaystyle \begin{aligned} \begin{array}{rcl} \int \kappa \times \mathcal{N}(x; \bar{\eta} + A^{\mathsf{T}} \eta_a, \bar{\Omega} + A^{\mathsf{T}} \Omega_a A ) \text{d}x = \kappa \end{array} \end{aligned} $$
(14.64)

Hence κ is the result of a convolution of two Gaussian distributions, which can be computed as [68, page 209]

$$\displaystyle \begin{aligned} \begin{array}{lll} \kappa = \mathcal{N}_{\mathcal{P}}(\Omega_a^{-1} \eta_a; A \bar{\Omega}^{-1} \bar{\eta}, A \bar{\Omega}^{-1} A^{\mathsf{T}} + \Omega_a^{-1}) \end{array} \end{aligned} $$
(14.65)

and this concludes the proof. □

Detection (b it = 1)

Let us start from the general update Eq. (14.19):

$$\displaystyle \begin{aligned} {\mathbb P}\left(y_{1:t+1} | Z_{1:t+1}\right) = \frac{ {\mathbb P}\left(z_{t+1} | y_{1:t+1} \right) {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) }{ \int {\mathbb P}\left(z_{t+1} | y_{1:t+1} \right) {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) dy_{1:t+1} } \end{aligned} $$
(14.66)

Let us focus on the term \({\mathbb P}\left (z_{t+1} | y_{1:t+1} \right ) {\mathbb P}\left (y_{1:t+1} | Z_{1:t}\right )\). First of all, we rewrite the measurement likelihood as:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} {\mathbb P}\left( b_{it}=1 | y_{1:t}\right) = \exp{ \left\{ -\frac{ \|p^y_{\tau_{it}} - s_i \|{}^2}{r^2} \right\} } = \\ \exp{ \left\{ -\frac{ \|U_{1:t+1} y_{1:t+1} - s_i \|{}^2}{r^2} \right\} } = \frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \end{array} \end{aligned} $$
(14.67)

which stresses the fact that the measurement likelihood can be seen as a “scaled” multivariate Gaussian, with γ being the normalization factor (the expression of this term is irrelevant for the subsequent derivation). Let us now substitute the prior probability (14.16) and the measurement likelihood (14.67) in (14.66):

$$\displaystyle \begin{aligned} \begin{array}{lll} {} \frac{ {\mathbb P}\left(z_{t+1} | y_{1:t+1} \right) {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) }{ \int {\mathbb P}\left(z_{t+1} | y_{1:t+1} \right) {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) dy_{1:t+1} } = \\ {} \frac{ \frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ \int \frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j} ) dy_{1:t+1} } = \\ {} \frac{ \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ \int \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) dy_{1:t+1} } = \\ {} \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ \int \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) dy_{1:t+1} } \end{array} \end{aligned} $$

which, using Lemma 2, becomes:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \; \beta_{t+1,j} \; \mathcal{N}(y_{1:t+1} \; ; \; {\eta}_{t+1,j}, {\Omega}_{t+1,j} ) }{ \int \sum_{j=1}^m \bar{\alpha}_{t+1,j} \; \beta_{t+1,j} \; \mathcal{N}(y_{1:t+1} \; ; \; {\eta}_{t+1,j}, {\Omega}_{t+1,j} ) dy_{1:t+1} } \end{array} \end{aligned} $$
(14.68)

where η t+1,j and Ωt+1,j are defined as in (14.25). Observing that the integral of each Gaussian at the denominator of (14.68) is one, the previous simplifies to

$$\displaystyle \begin{aligned} \begin{array}{lll} \left( \frac{\bar{\alpha}_{t+1,j} \; \beta_{t+1,j} }{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \; \beta_{t+1,j} } \right) \mathcal{N}(y_{1:t+1} \; ; \; {\eta}_{t+1,j}, {\Omega}_{t+1,j} ) \end{array} \end{aligned} $$
(14.69)

which matches the expression of (14.25).

No detection (b it = 0)

In this case, the measurement likelihood is:

$$\displaystyle \begin{aligned} \begin{array}{lll} {} {\mathbb P}\left( b_{it}=0 | y_{1:t}\right) = 1- \exp{ \left\{ -\frac{ \|p^y_{\tau_{it}} - s_i \|{}^2}{r^2} \right\} } = 1 - \frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \end{array} \end{aligned} $$
(14.70)

where γ = 2πr 2 (this is the inverse of the normalization factor of the Gaussian).

Let us now substitute the prior probability (14.16) and the measurement likelihood (14.70) in (14.66):

$$\displaystyle \begin{aligned} \begin{array}{lll} {} \frac{ {\mathbb P}\left(z_{t+1} | y_{1:t+1} \right) {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) }{ \int {\mathbb P}\left(z_{t+1} | y_{1:t+1} \right) {\mathbb P}\left(y_{1:t+1} | Z_{1:t}\right) dy_{1:t+1} } = \\ {} \frac{ (1-\frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} )) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ \int (1-\frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} )) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j} ) dy_{1:t+1} } = \\ \\ {\mbox{(integral of the GMM at the denominator is 1)} } \\ \\ \frac{ (1-\frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} )) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \int \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j},\bar{\Omega}_{t+1,j}) dy_{1:t+1} } = \end{array} \end{aligned} $$
$$\displaystyle \begin{aligned} \begin{array}{lll} {\mbox{(from the definition of} {\beta_{t+1,j})} } \\ \\ \frac{ (1-\frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } = \\ {} \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } -\\ {} \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } = \\ \\ {\mbox{(note that gamma does not simplify)} } \\ \\ \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } -\\ {} \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \mathcal{N}(U_{1:t+1} y_{1:t+1} \; ; \frac{s_i}{r^2} , \frac{1}{r^2} ) \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } = \\ \\ {\mbox{(using Lemma \mbox{2} in each term of the second sum)} } \\ \\ \frac{ \sum_{j=1}^m \bar{\alpha}_{t+1,j} }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j}, \bar{\Omega}_{t+1,j}) + \\ {} \frac{ \sum_{j=1}^m - \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} }{ 1 - \sum_{j=1}^m \bar{\alpha}_{t+1,j} \frac{1}{\gamma} \beta_{t+1,j} } \mathcal{N}(y_{1:t+1} \; ; \; \bar{\eta}_{t+1,j} + U_{1:t+1}^{\mathsf{T}} \frac{s_i}{r^2}, \bar{\Omega}_{t+1,j} + \frac{1}{r^2} U_{1:t+1}^{\mathsf{T}} U_{1:t+1}) \end{array} \end{aligned} $$

which coincides with (14.25).

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Carlone, L., Axelrod, A., Karaman, S., Chowdhary, G. (2018). Aided Optimal Search: Data-Driven Target Pursuit from On-Demand Delayed Binary Observations. In: Blasch, E., Ravela, S., Aved, A. (eds) Handbook of Dynamic Data Driven Applications Systems. Springer, Cham. https://doi.org/10.1007/978-3-319-95504-9_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-95504-9_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-95503-2

  • Online ISBN: 978-3-319-95504-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation