Abstract
This paper considers persistent monitoring of environmental phenomena using unmanned aerial vehicles (UAVs). The objective is to generate periodic dynamically feasible UAV trajectories that minimize the estimation uncertainty at a set of points of interest in the environment. We develop an optimization algorithm that iterates between determining the observation periods for a set of ordered points of interest and optimizing a continuous UAV trajectory to meet the required observation periods and UAV dynamics constraints. The interest-point visitation order is determined using a Traveling Salesman Problem (TSP), followed by a greedy optimization algorithm to determine the number of observations that minimizes the maximum steady-state eigenvalue of a Kalman filter estimator. Given the interest-point observation periods and visitation order, a minimum-jerk trajectory is generated from a bi-level optimization, formulated as a convex quadratically constrained quadratic program. The resulting B-spline trajectory is guaranteed to be feasible, meeting the observation duration, maximum velocity and acceleration, region enter and exit constraints. The feasible trajectories outperform existing methods by achieving comparable observability at up to 47% higher travel speeds, resulting in lower maximum estimation uncertainty.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Code Availability
The custom code used for generating the results found in this paper can be accessed at https://github.com/UCSD-SEELab/persistent-monitoring.
References
Alvear, O., Zema, N.R., Natalizio, E., Calafate, C.T.: Using uav-based systems to monitor air pollution in areas with poor accessibility. J. Adv. Transp. 2017. https://doi.org/10.1155/2017/8204353 (2017)
Alvear, O., Calafate, C.T., Zema, N.R., Natalizio, E., Hernández-Orallo, E., Cano, J. -C., Manzoni, P.: A discretized approach to air pollution monitoring using uav-based sensing. Mob. Netw. Appl. 23(6), 1693–1702 (2018). https://doi.org/10.1007/s11036-018-1065-4
Allison, R.S., Johnston, J.M., Craig, G., Jennings, S.: Airborne optical and thermal remote sensing for wildfire detection and monitoring. Sensors 16(8), 1310 (2016). https://doi.org/10.3390/s16081310
Bushnaq, O.M., Chaaban, A., Al-Naffouri, T.Y.: The role of uav-iot networks in future wildfire detection. IEEE Internet of Things Journal. https://doi.org/10.1109/JIOT.2021.3077593 (2021)
Aslan, Y.E., Korpeoglu, I., Ulusoy, Ö.: A framework for use of wireless sensor networks in forest fire detection and monitoring. Comput. Environ. Urban. Syst. 36(6), 614–625 (2012). https://doi.org/10.1016/j.compenvurbsys.2012.03.002
Le Ny, J., Feron, E., Dahleh, M.A.: Scheduling continuous-time kalman filters. IEEE Trans. Autom. Control 56(6), 1381–1394 (2011). https://doi.org/10.1109/TAC.2010.2095970
Jawaid, S.T., Smith, S.L.: Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems. Automatica 61, 282–288 (2015). https://doi.org/10.1016/j.automatica.2015.08.022
Asghar, A.B., Jawaid, S.T., Smith, S.L.: A complete greedy algorithm for infinite-horizon sensor scheduling. Automatica 81, 335–341 (2017). https://doi.org/10.1016/j.automatica.2017.04.018
Zhang, H., Ayoub, R., Sundaram, S.: Sensor selection for kalman filtering of linear dynamical systems: complexity, limitations and greedy algorithms. Automatica 78, 202–210 (2017). https://doi.org/10.1016/j.automatica.2016.12.025
Justice, C., Giglio, L., Korontzi, S., Owens, J., Morisette, J., Roy, D., Descloitres, J., Alleaume, S., Petitcolin, F., Kaufman, Y.: The modis fire products. Remote Sens. Environ. 83(1-2), 244–262 (2002). https://doi.org/10.1016/S0034-4257(02)00076-7
Koltunov, A., Ustin, S.L., Prins, E.M.: On timeliness and accuracy of wildfire detection by the goes wf-abba algorithm over california during the 2006 fire season. Remote Sens. Environ. 127, 194–209 (2012). https://doi.org/10.1016/j.rse.2012.09.001
Schroeder, W., Oliva, P., Giglio, L., Csiszar, I.A.: The new viirs 375 m active fire detection data product: Algorithm description and initial assessment. Remote Sens. Environ. 143, 85–96 (2014). https://doi.org/10.1016/j.rse.2013.12.008
Koltunov, A., Ustin, S.L., Quayle, B., Schwind, B., Ambrosia, V.G., Li, W.: The development and first validation of the goes early fire detection (goes-efd) algorithm. Remote Sens. Environ. 184, 436–453 (2016). https://doi.org/10.1016/j.rse.2016.07.021
Smith, S.L., Schwager, M., Rus, D.: Persistent robotic tasks: Monitoring and sweeping in changing environments. IEEE Trans. Robot. 28(2), 410–426 (2012). https://doi.org/10.1109/TRO.2011.2174493
Cassandras, C.G., Lin, X., Ding, X.: An optimal control approach to the multi-agent persistent monitoring problem. IEEE Trans. Autom. Control 58(4), 947–961 (2013). https://doi.org/10.1109/TAC.2012.2225539
Song, C., Liu, L., Feng, G., Xu, S.: Optimal control for multi-agent persistent monitoring. Automatica 50(6), 1663–1668 (2014). https://doi.org/10.1016/j.automatica.2014.04.011
Atanasov, N., Le Ny, J., Daniilidis, K., Pappas, G.J.: Information Acquisition with Sensing Robots: Algorithms and Error Bounds. In: Robotics and Automation (ICRA), IEEE International Conference On, Pp. 6447–6454. https://doi.org/10.1109/ICRA.2014.6907811 (2014)
Lin, X., Cassandras, C.G.: An optimal control approach to the multi-agent persistent monitoring problem in two-dimensional spaces. IEEE Trans. Autom. Control 60(6), 1659–1664 (2015). https://doi.org/10.1109/TAC.2014.2359712
Lan, X., Schwager, M.: Rapidly exploring random cycles: Persistent estimation of spatiotemporal fields with multiple sensing robots. IEEE Trans. Robot. 32(5), 1230–1244 (2016). https://doi.org/10.1109/TRO.2016.2596772
Zhou, N., Cassandras, C.G., Yu, X., Andersson, S.B.: Optimal event-driven multi-agent persistent monitoring with graph-limited mobility. IFAC-PapersOnLine 50(1), 2181–2186 (2017)
Yu, X., Andersson, S.B., Zhou, N., Cassandras, C.G.: Optimal dwell times for persistent monitoring of a finite set of targets. In: American Control Conference (ACC). https://doi.org/10.23919/ACC.2017.7963817, vol. 2017, pp 5544–5549. IEEE (2017)
Ostertag, M., Atanasov, N., Rosing, T.: Robust velocity control for minimum steady state uncertainty in persistent monitoring applications. In: 2019 American Control Conference (ACC). https://doi.org/10.23919/ACC.2019.8814376, pp 2501–2508. IEEE (2019)
Pinto, S.C., Andersson, S.B., Hendrickx, J.M., Cassandras, C.G.: Optimal periodic multi-agent persistent monitoring of a finite set of targets with uncertain states. In: 2020 American Control Conference (ACC). https://doi.org/10.23919/ACC45564.2020.9147376, pp 5207–5212. IEEE (2020)
Metia, S., Oduro, S., Sinha, A.: Pollutant profile estimation using unscented Kalman filter. In: Advances in Control, Signal Processing and Energy Systems. https://doi.org/10.1007/978-981-32-9346-5_2, pp 17–28. Springer (2020)
Garg, S., Ayanian, N.: Persistent monitoring of stochastic spatio-temporal phenomena with a small team of robots. In: Robotics: Science and Systems (RSS) Conference. https://doi.org/10.15607/RSS.2014.X.038, vol. 2014. Robotics: Science and Systems (2014)
Zhao, S., Ma, Y., Huang, B.: Probabilistic monitoring of sensors in state-space with variational bayesian inference. IEEE Trans. Ind. Electron. 66(3), 2154–2163 (2018). https://doi.org/10.1109/TIE.2018.2838088
Kiefer, J.: Optimum experimental designs. Journal of the Royal Statistical Society: Series B (Methodological) 21(2), 272–304 (1959). https://doi.org/10.1111/j.2517-6161.1959.tb00338.x
Yang, C., Kaplan, L., Blasch, E.: Performance measures of covariance and information matrices in resource management for target state estimation. IEEE Trans. Aerosp. Electron. Syst. 48(3), 2594–2613 (2012). https://doi.org/10.1109/TAES.2012.6237611
Zhao, L., Zhang, W., Hu, J., Abate, A., Tomlin, C.J.: On the optimal solutions of the infinite-horizon linear sensor scheduling problem. IEEE Trans. Autom. Control 59(10), 2825–2830 (2014). https://doi.org/10.1109/TAC.2014.2314222
Hari, S.K.K., Rathinam, S., Darbha, S., Kalyanam, K., Manyam, S.G., Casbeer, D.: Bounding algorithms for persistent monitoring of targets using unmanned vehicles. In: 2019 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 615–621. https://doi.org/10.1109/ICUAS.2019.8798134 (2019)
Hari, S.K.K., Rathinam, S., Darbha, S., Kalyanam, K., Manyam, S.G., Casbeer, D.: Persistent monitoring of dynamically changing environments using an unmanned vehicle (2018)
Joshi, S., Boyd, S.: Sensor selection via convex optimization. IEEE Trans. Signal Process. 57 (2), 451–462 (2008). https://doi.org/10.1109/TSP.2008.2007095
Tang, L., Shao, G.: Drone remote sensing for forestry research and practices. J. Forestry Res. 26(4), 791–797 (2015). https://doi.org/10.1007/s11676-015-0088-y
Portugal, D., Pippin, C., Rocha, R.P., Christensen, H.: Finding optimal routes for multi-robot patrolling in generic graphs. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 363–369. https://doi.org/10.1109/IROS.2014.6942585 (2014)
Kant, K., Zucker, S.W.: Toward efficient trajectory planning: The path-velocity decomposition. Int. J. Robot. Res. 5(3), 72–89 (1986). https://doi.org/10.1177/027836498600500304
Yu, J., Schwager, M., Rus, D.: Correlated orienteering problem and its application to persistent monitoring tasks. IEEE Trans. Robot. 32(5), 1106–1118 (2016). https://doi.org/10.1109/TRO.2016.2593450
Hollinger, G.A., Sukhatme, G.S.: Sampling-based robotic information gathering algorithms. Int. J. Robot. Res. 33(9), 1271–1287 (2014). https://doi.org/10.1177/0278364914533443
Ghaffari Jadidi, M., Valls Miro, J., Dissanayake, G.: Sampling-based incremental information gathering with applications to robotic exploration and environmental monitoring. Int. J. Robot. Res. 38(6), 658–685 (2019). https://doi.org/10.1177/0278364919844575
Atanasov, N., Le Ny, J., Daniilidis, K., Pappas, G.J.: Decentralized active information acquisition: Theory and application to multi-robot slam. In: 2015 IEEE International Conference on Robotics and Automation (ICRA). https://doi.org/10.1109/ICRA.2015.7139863, pp 4775–4782. IEEE (2015)
Mueller, M.W., Hehn, M., D’Andrea, R.: A computationally efficient motion primitive for quadrocopter trajectory generation. IEEE Trans. Robot. 31(6), 1294–1310 (2015). https://doi.org/10.1109/TRO.2015.2479878
Liu, S., Atanasov, N., Mohta, K., Kumar, V.: Search-based motion planning for quadrotors using linear quadratic minimum time control. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). https://doi.org/10.1109/IROS.2017.8206119, pp 2872–2879. IEEE (2017)
Mellinger, D., Kumar, V.: Minimum snap trajectory generation and control for quadrotors. In: 2011 IEEE International Conference on Robotics and Automation. https://doi.org/10.1109/ICRA.2011.5980409, pp 2520–2525. IEEE (2011)
Tang, M., Tong, R., Wang, Z., Manocha, D.: Fast and Exact Continuous Collision Detection with Bernstein Sign Classification. ACM Transactions on Graphics 33(6). https://doi.org/10.1145/2661229.2661237 (2014)
Richter, C., Bry, A., Roy, N.: Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments. In: Inaba, M., Corke, P. (eds.) Robotics Research: The 16th International Symposium ISRR. Springer Tracts in Advanced Robotics. https://doi.org/10.1007/978-3-319-28872-7_37, pp 649–666. Springer (2016)
Tang, S., Kumar, V.: Autonomous flight. Annual Review of Control Robotics, and Autonomous Systems 1(1), 29–52 (2018). https://doi.org/10.1146/annurev-control-060117-105149
Liu, S., Watterson, M., Mohta, K., Sun, K., Bhattacharya, S., Taylor, C.J., Kumar, V.: Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-D complex environments. IEEE Robotics and Automation Letters 2(3), 1688–1695 (2017). https://doi.org/10.1109/LRA.2017.2663526
Liu, S., Mohta, K., Atanasov, N., Kumar, V.: Search-Based motion planning for aggressive flight in SE(3). IEEE Robot. Autom. Lett. 3(3), 2439–2446 (2018). https://doi.org/10.1109/LRA.2018.2795654
Van Nieuwstadt, M.J., Murray, R.M.: Real-time trajectory generation for differentially flat systems. International Journal of Robust and Nonlinear Control 8(11), 995–1020 (1998). https://doi.org/10.1002/(SICI)1099-1239(199809)8:11%3C995::AID-RNC373%3E3.0.CO;2-W
Ding, W., Gao, W., Wang, K., Shen, S.: An Efficient B-spline-Based Kinodynamic Replanning Framework for Quadrotors. https://doi.org/10.1109/TRO.2019.2926390 (2019)
Zhou, B., Gao, F., Wang, L., Liu, C., Shen, S.: Robust and efficient quadrotor trajectory generation for fast autonomous flight. IEEE Robotics and Automation Letters 4(4), 3529–3536 (2019). https://doi.org/10.1109/LRA.2019.2927938
Tzoumas, V., Jadbabaie, A., Pappas, G.J.: Sensor placement for optimal kalman filtering: Fundamental limits, submodularity, and algorithms. In: 2016 American Control Conference (ACC). https://doi.org/10.1109/ACC.2016.7524914, pp 191–196. IEEE (2016)
Chamon, L.F., Pappas, G.J., Ribeiro, A.: Approximate supermodularity of kalman filter sensor selection. IEEE Trans. Autom. Control 66(1), 49–63 (2020). https://doi.org/10.1109/TAC.2020.2973774
Chu, E.-W., Fan, H.-Y., Lin, W.-W.: A structure-preserving doubling algorithm for continuous-time algebraic riccati equations. Linear Algebra and Its Applications 396, 55–80 (2005). https://doi.org/10.1016/j.laa.2004.10.010
Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Concorde TSP solver (2006)
MOSEK ApS: MOSEK Optimizer API for Python 9.3.7. https://docs.mosek.com/latest/pythonapi/index.html(2019)
Lee, T., Leok, M., McClamroch, N.H.: Geometric tracking control of a quadrotor uav on se (3). In: 49th IEEE Conference on Decision and Control (CDC). https://doi.org/10.1109/CDC.2010.5717652, pp 5420–5425. IEEE (2010)
Funding
We gratefully acknowledge support from the National Science Foundation National Robotics Initiative (CNS-1830399).
Author information
Authors and Affiliations
Contributions
Conceptualization: Michael H. Ostertag, Nikolay Atanasov; Methodology: Michael H. Ostertag, Nikolay Atanasov; Software, investigation, and analysis: Michael H. Ostertag; Writing - original draft preparation: Michael H. Ostertag; Writing - review and editing: Michael H. Ostertag, Nikolay Atanasov, Tajana Rosing; Supervision: Nikolay Atanasov, Tajana Rosing
Corresponding author
Ethics declarations
Conflict of Interests
The authors have no relevant financial or non-financial interests to disclose.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
1.1 A.1 GKA Stopping Criterion (Section 4.3)
For uncorrelated POIs, each additional observation results in a decrease in the eigenvalue of estimation uncertainty for a POI, such that \(\lambda ^{(d_{i}-1, a)}_{i} > \lambda ^{(d_{i}, a)}_{i}\) where \(\lambda ^{(d_{i}, a)}_{i}\) is the eigenvalue associated with the estimation uncertainty of POI qi for di observations and a total observations. An additional observation of a different point qj results in an uncertainty increase as \(\lambda ^{(d_{i}, a + 1)}_{i} > \lambda ^{(d_{i}, a)}_{i} + w_{i} f_{s}^{{-1}}\) for j≠i. To see this relationship, note that \(\lambda ^{(d_{i}, a)}_{i} = \rho (\lambda ^{(d_{i}, a)}_{i}) + a w_{i} f_{s}^{{-1}}\) where ρ(⋅) is the reduction in uncertainty due to an added observation, a known monotonic function.
When a POI meets the stopping condition \(\lambda ^{(d_{i}^{*}, a)}_{i} - \lambda ^{(d_{i}^{*}+1, a+1)}_{i} < w_{i} f_{s}^{{-1}}\), then it follows that \(\lambda ^{(d_{i}^{*}, a)}_{i} < \lambda ^{(d_{i}^{*}+1, a+1)}_{i} + w_{i} f_{s}^{{-1}} < \lambda ^{(d^{*}+1, a+2)}_{i}\), which states that when the stopping condition is met, the uncertainty λi can only increase after the set of observations at qi and at any other POI. In GKA, an observation is added to the POI with the highest uncertainty. When any two or more POI meet the stopping condition, then adding an observation to any POI that meets the stopping criterion will result in an overall increase in uncertainty.
1.2 A.2 B-Spline Derivatives (Section 5.1)
The derivative for a B-spline is defined as:
For uniform spacing Δτ = τj + 1 − τj, the derivative simplifies as:
where A(1) captures the interaction between basis functions. With A(a) capturing the linear interaction between basis functions for derivative a, further derivatives take the form:
1.3 A.3 B-Spline Objective Reformulation (Section 5.2)
The primary objective from from Eq. 28a can be simplified by noting that \(T_{i \rightarrow i + 1}\) is constant and will not affect the minimization goal and that Ti = MiΔτi. The secondary objective, the average jerk power, can be replaced by the linear combination of control points and bases in Eq. 27. The result is an updated cost function as follows:
The secondary objective can be further modified for the specific case of minimizing the square of jerk magnitude for k = 4. For a 4rd-order representation of position, the 3rd derivative results in a basis function of order 1, which is either 1 for τi ≤ t < τi + 1 and 0 otherwise as shown in Eq. 25. Since the limited domain of the base does not overlap with any other base, the outer product of the 0th-order basis function results in I and the integral results in ΔτI, where I is the identity matrix as seen below:
Since 𝜖 is an arbitrarily small scale factor, we incorporate 1/Mi and 1/Δτ5 into 𝜖, resulting in the reformulated objective:
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Ostertag, M., Atanasov, N. & Rosing, T. Trajectory Planning and Optimization for Minimizing Uncertainty in Persistent Monitoring Applications. J Intell Robot Syst 106, 2 (2022). https://doi.org/10.1007/s10846-022-01676-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-022-01676-3