This article considers the optimal estimation of the state of a dynamic observable using a mobile sensor. The main goal is to compute a sensor trajectory that minimizes the estimation error over a given time horizon taking into account uncertainties in the observable dynamics and sensing, and respecting the constraints of the workspace. The main contribution is a methodology for handling arbitrary dynamics, noise models, and environment constraints in a global optimization framework. It is based on sequential Monte Carlo methods and sampling-based motion planning. Three variance reduction techniques–utility sampling, shuffling, and pruning–based on importance sampling, are proposed to speed up convergence. The developed framework is applied to two typical scenarios: a simple vehicle operating in a planar polygonal obstacle environment and a simulated helicopter searching for a moving target in a 3-D terrain.
BethkeBBertuccelliLFHowJP (2008) Experimental demonstration of adaptive MDP-based planning with model uncertainty. In: AIAA Guidance, Navigation and Control Conference.
2.
BrysonMSukkariehS (2009) Architectures for cooperative airborne simultaneous localisation and mapping. Journal of Intelligent and Robotic Systems, Special Issue on Airborne SLAM, 55: 267–297.
3.
BurnsBBrockO (2005) Toward optimal configuration space sampling. In: Robotics: Science and Systems.
4.
CelesteFDambrevilleFCadreJ-PL (2007) Optimal path planning using cross-entropy method. In: 2006 9th International Conference on Information Fusion, 1–8.
5.
ChosetHLynchKMHutchinsonSKantorGABurgardWKavrakiLEThrunS (2005) Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.
6.
ChungTHBurdickJW (2007) A decision-making framework for control strategies in probabilistic search. In: Intl. Conference on Robotics and Automation. ICRA, 4386–4393.
7.
ClarkeFHLedyaevYSSternRJWolenskiPR (1998) Nonsmooth Analysis and Control Theory. Springer.
8.
ColeDTGoktoganAHSukkariehS (2008) The demonstration of a cooperative control architecture for UAV teams. In: Experimental Robotics. Berlin, Heidelberg: Springer, vol. 39, 501–510.
9.
de GeeterJde SchutterJBruyninckxHvan BrusselHDecretonM (1998) Tolerance-weighted L-optimal experiment design for active sensing. In: Proc. Conf. IEEE/RSJ Int Intelligent Robots and Systems, vol. 3, 1670–1675.
10.
Del MoralP (2004) Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Springer-Verlag.
11.
DoucetAde FreitasNGordonN (eds) (2001) Sequential Monte Carlo Methods in Practice.
12.
ErincGCarpinS (2007) A genetic algorithm for nonholonomic motion planning. In: Proc. IEEE Int Robotics and Automation Conf, 1843–1849.
13.
FrazzoliEDahlehMAFeronE (2002) Real-time motion planning for agile autonomous vehicles. AIAA Journal of Guidance, Control, and Dynamics25: 116–129.
14.
FrazzoliEDahlehMAFeronE (2005) Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Transactions on Robotics21: 1077–1091.
15.
GeyerC (2008) Active target search from UAVs in urban environments. In: Proc. IEEE International Conference on Robotics and Automation. ICRA, 2366–2371.
16.
GottschalkSLinMCManochaD (1996) OBBTree: A hierarchical structure for rapid interference detection. Eurographics/ACM SIGGRAPH Symposium on Computer Animation, 30: 171–180.
17.
GrocholskyBMakarenkoADurrant-WhyteH (2003) Information-theoretic coordinated control of multiple sensor platforms. In: Proc. IEEE International Conference on Robotics and Automation. ICRA, vol. 1, 1521–1526.
18.
HeRPrenticeSRoyN (2008) Planning in information space for a quadrotor helicopter in a GPS-denied environments. In: Proceedings of the IEEE International Conference on Robotics and Automation. ICRA, 1814–1820.
19.
HocaogluCSandersonAC (2001) Planning multiple paths with evolutionary speciation. IEEE Transactions on Evolutionary Computing5: 169–191.
20.
HoffmannGMTomlinCJ (2010) Mobile sensor network control using mutual information methods and particle filters. IEEE Transactions on Automatic Control55(1): 32–47.
21.
HollingerGSinghSKehagiasA (2009) Efficient, guaranteed search with multi-agent teams. In: Robotics: Science and Systems.
22.
HsuDKindelRLatombeJRockS (2002) Randomized kinodynamic motion planning with moving obstacles. Int. J. Robotics Research21: 233–255.
23.
KobilarovM (2008) Discrete Geometric Motion Control of Autonomous Vehicles. PhD thesis, University of Southern California.
24.
KobilarovM (2011) Cross-entropy randomized motion planning. In: Proceedings of Robotics: Science and Systems, Los Angeles, CA, USA.
25.
KrauseAGuestrinC (2007) Nonmyopic active learning of Gaussian processes: an exploration-exploitation approach. In: International Conference on Machine Learning (ICML), Corvallis, Oregon.
26.
LaddAKavrakiL (2004) Measure theoretic analysis of probabilistic path planning. IEEE Transactions on Robotics and Automation20: 229–242.
27.
LangdonWBPoliR (2001) Foundations of Genetic Programming. Springer.
LaValleSM (2006) Planning Algorithms. Cambridge, UK: Cambridge University Press.
30.
LavisBFurukawaTWhyteHFD (2008) Dynamic space reconfiguration for Bayesian search and tracking with moving targets. Auton. Robot24: 387–399.
31.
MarsdenJWestM. (2001). Discrete mechanics and variational integrators. Acta Numerica10: 357–514.
32.
Martinez-CantinRde FreitasNBrochuECastellanosJDoucetA (2009) A Bayesian exploration–exploitation approach for optimal online sensing and planning with a visually guided mobile robot. Auton. Robot27: 93–103.
MihaylovaLLefebvreTBruyninckxHGadeyneKSchutterJD (2003a) A comparison of decision making criteria and optimization methods for active robotic sensing. In: Lecture Notes in Computer Science, vol. LNCS 2542, 316–324.
35.
MihaylovaLSchutterJDBruyninckxH (2003b) A multisine approach for trajectory optimization based on information gain. Robotics and Autonomous Systems43: 231–243.
36.
ParisSLe CadreJ-P (2002) Planning for terrain-aided navigation. In: Proc. 5th Int Information Fusion Conf., vol. 2, 1007–1014.
37.
PowellW (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley Series in Probability and Statistics.
38.
RobertCPCasellaG (2004) Monte Carlo Statistical Methods. Springer.
39.
RubinsteinRYKroeseDP (2008) Simulation and the Monte Carlo Method. Wiley.
40.
RubinsteinRYKroeseDP (2004) The cross-entropy method: a unified approach to combinatorial optimization. Springer.
41.
RyanA (2008) Information-theoretic tracking control based on particle filter estimate. In: AIAA Guidance, Navigation, and Control Conf.
42.
SimRRoyN (2005) Global A-optimal robot exploration in SLAM. In: Proc. IEEE Int. Conf. Robotics and Automation. ICRA, 661–666.
43.
SinghSSKantasNVoB-NDoucetAEvansRJ (2007) Simulation-based optimal sensor scheduling with application to observer trajectory planning. Automatica43: 817–830.
44.
StachnissCGrisettiGBurgardW (2005) Information gain-based exploration using Rao–Blackwellized particle filters. In: Robotics: Science and Systems.
45.
ThrunSBurgardWFoxD (2005) Probabilistic Robotic. MIT Press.
TremoisOLe CadreJ-P (1999) Optimal observer trajectory in bearings-only tracking for maneuvering sources. IEEE Proceedings – Radar, Sonar and Navigation146: 31–39.
48.
VaidyanathanRHocaogluCPrinceTSQuinnRD (2001) Evolutionary path planning for autonomous air vehicles using multi-resolution path representation. In: Proc. IEEE/RSJ Int Intelligent Robots and Systems Conf, vol. 1, 69–76.
49.
XiaoJMichalewiczZZhangLTrojanowskiK (1997) Adaptive evolutionary planner/navigator for mobile robots. IEEE Transactions on Evolutionary Computation1: 18–28.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
