Abstract
In this work, we consider the problem of localizing a team of robots, without access to direct pose measurements, under the influence of nonuniform environmental disturbances and measurement bias. Specifically, we are interested in the conditions under which teams remain range-only localizable when the environmental disturbances vary from robot to robot. We approach this problem through nonlinear observability and graph theory. After analyzing the system’s observability properties, we present theorems that identify the structural conditions under which the system maintains local weak observability. We demonstrate that rigid structures are important not only in defining multi-robot interactions, but also in characterizing the influence of nonuniform disturbances. We also give several example systems to cement intuition on the derived conditions. An observability-based planner is then presented that guides a subset of robots toward trajectories that are highly observable through finite-horizon optimization on robot headings. Simulations are then presented, along with an extended Kalman filter for state estimation, and a comparison to previous methods, to corroborate and demonstrate the results derived.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alaeddini, A. (2016). Observability-based approach to design, analysis and optimization of dynamical systems. Ph.D. thesis, William E. Boeing Department of Aeronautics and Astronautics.
Alessandretti, A., Aguiar, A. P., & Jones, C. N. (2015). Optimization based control for target estimation and tracking via highly observable trajectories. In CONTROLO’2014-Proceedings of the 11th Portuguese Conference on Automatic Control (pp 495–504). Springer
Arrichiello, F., Antonelli, G., Aguiar, A. P., & Pascoal, A. (2013). An observability metric for underwater vehicle localization using range measurements. Sensors, 13(12), 16191–16215. https://doi.org/10.3390/s131216191.
Bahr, A., Leonard, J. J., & Fallon, M. F. (2009). Cooperative localization for autonomous underwater vehicles. The International Journal of Robotics Research, 28(6), 714–728.
Bayat, M., Crasta, N., Aguiar, A. P., & Pascoal, A. M. (2015). Range-based underwater vehicle localization in the presence of unknown ocean currents: theory and experiments. IEEE Transactions on Control Systems Technology, 24(1), 122–139.
Chitre, M. (2010). Path planning for cooperative underwater range-only navigation using a single beacon. In 2010 International conference on autonomous and intelligent systems (AIS) (pp 1–6). IEEE.
Chowdhary, G., Johnson, E. N., Magree, D., Wu, A., & Shein, A. (2013). Gps-denied indoor and outdoor monocular vision aided navigation and control of unmanned aircraft. Journal of Field Robotics, 30(3), 415–438.
Christou, N. T. (1990). On the space-time ocean current variability and its effects on the length-of-day. Ph.D. thesis, Fredericton: Department of Surveying Engineering, University of New Brunswick
De Palma, D., Indiveri, G., & Parlangeli, G. (2015a). Multi-vehicle relative localization based on single range measurements. IFAC-PapersOnLine, 48(5), 17–22.
De Palma, D., Indiveri, G., & Pascoal, A. M. (2015b). A null-space-based behavioral approach to single range underwater positioning. IFAC-PapersOnLine, 48(16), 55–60.
Ellenberg, A., Kontsos, A., Moon, F., & Bartoli, I. (2016). Bridge related damage quantification using unmanned aerial vehicle imagery. Structural Control and Health Monitoring, 23(9), 1168–1179.
Fekete, Z., Jordán, T., & Whiteley, W. (2004). An inductive construction for plane laman graphs via vertex splitting. In European symposium on algorithms (pp 299–310). Springer
Gadre, A. S., & Stilwell, D. (2005). Underwater navigation in the presence of unknown currents based on range measurements from a single location. In American Control Conference, 2005. Proceedings of the 2005 (pp. 656–661). IEEE.
Gadre, A. S., & Stilwell, D. J. (2004). Toward underwater navigation based on range measurements from a single location. In 2004. Proceedings. ICRA’04. 2004 IEEE international conference on robotics and automation (Vol. 5, pp. 4472–4477). IEEE.
Glotzbach, T., Crasta, N., & Ament, C. (2014). Observability analyses and trajectory planning for tracking of an underwater robot using empirical gramians. IFAC Proceedings Volumes, 47(3), 4215–4221. https://doi.org/10.3182/20140824-6-ZA-1003.01939.
Hausman, K., Preiss, J., Sukhatme, G. S., & Weiss, S. (2017). Observability-aware trajectory optimization for self-calibration with application to UAVs. IEEE Robotics and Automation Letters, 2(3), 1770–1777.
Heintzman, L. L., & Williams, R. K. (2018). Nonlinear observability of unicycle multi-agent teams subject to sensor bias and environmental disturbance. In 2018 IEEE 57th annual conference on decision and control (CDC).
Hermann, R., & Krener, A. (1977). Nonlinear controllability and observability. IEEE Transactions on Automatic Control, 22(5), 728–740.
Hesch, J. A., Kottas, D. G., Bowman, S. L., & Roumeliotis, S. I. (2014). Camera-imu-based localization: Observability analysis and consistency improvement. The International Journal of Robotics Research, 33(1), 182–201.
Khalil, H. (2002). Nonlinear systems (3rd ed.). Upper Saddle River, NJ: Prentice Hall.
Kia, S. S., Hechtbauer, J., Gogokhiya, D., & Martínez, S. (2018). Server-assisted distributed cooperative localization over unreliable communication links. IEEE Transactions on Robotics, 99, 1–8.
Krener, A. J., & Ide, K. (2009). Measures of unobservability. In: Proceedings of the 48th IEEE conference on decision and control, 2009 held jointly with the 2009 28th Chinese control conference. CDC/CCC 2009 (pp. 6401–6406). IEEE.
Laman, G. (1970). On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4(4), 331–340.
Monshizadeh, N., Trentelman, H. L., & Camlibel, M. K. (2014). Projection-based model reduction of multi-agent systems using graph partitions. IEEE Transactions on Control of Network Systems, 1(2), 145–154.
Olfati-Saber, R., & Jalalkamali, P. (2011). Collaborative target tracking using distributed Kalman filtering on mobile sensor networks. In American control conference (ACC), 2011 (pp. 1100–1105). IEEE.
Pierre, C., Chapuis, R., Aufrère, R., Laneurit, J., & Debain, C. (2018). Range-only based cooperative localization for mobile robots. In 2018 21st international conference on information fusion (FUSION) (pp. 1933–1939). IEEE.
Quenzer, J. D., & Morgansen, K. A. (2014). Observability based control in range-only underwater vehicle localization. In 2014 American control conference (pp. 4702–4707). https://doi.org/10.1109/ACC.2014.6859032.
Roumeliotis, S. I., & Bekey, G. A. (2002). Distributed multirobot localization. IEEE Transactions on Robotics and Automation, 18(5), 781–795.
Rui, G., & Chitre, M. (2010). Cooperative positioning using range-only measurements between two AUVs. In OCEANS 2010 IEEE-Sydney (pp 1–6). IEEE.
Saha, M., Ghosh, R., & Goswami, B. (2013). Robustness and sensitivity metrics for tuning the extended kalman filter. IEEE Transactions on Instrumentation and Measurement, 63(4), 964–971.
Soares, C., Ji, P., Gomes, J., & Pascoal, A. (2017). Diesel: Distributed self-localization of a network of underwater vehicles. In OCEANS 2017-Anchorage (pp. 1–6). IEEE.
Tay, T. S., & Whiteley, W. (1985). Generating isostatic frameworks. Structural Topology 1985 Núm 11.
Vander Hook, J., Tokekar, P., & Isler, V. (2015). Algorithms for cooperative active localization of static targets with mobile bearing sensors under communication constraints. IEEE Transactions on Robotics, 31(4), 864–876.
Webster, S. E. (2010). Decentralized single-beacon acoustic navigation: Combined communication and navigation for underwater vehicles. Tech rep, Johns Hopkins Univ Baltimore Md.
Webster, S. E., Eustice, R. M., Singh, H., & Whitcomb, L. L. (2012). Advances in single-beacon one-way-travel-time acoustic navigation for underwater vehicles. The International Journal of Robotics Research,. https://doi.org/10.1177/0278364912446166.
Williams, R. K., & Sukhatme, G. S. (2013). Constrained interaction and coordination in proximity-limited multiagent systems. IEEE Transactions on Robotics, 29(4), 930–944.
Williams, R. K., & Sukhatme, G. S. (2015). Observability in topology-constrained multi-robot target tracking. In 2015 IEEE international conference on robotics and automation (ICRA) (pp. 1795–1801). https://doi.org/10.1109/ICRA.2015.7139431
Williams, R. K., Gasparri, A., Priolo, A., & Sukhatme, G. S. (2013). Distributed combinatorial rigidity control in multi-agent networks. In 2013 IEEE 52nd annual conference on decision and control (CDC) (pp. 6061–6066). IEEE.
Williams, R. K., Gasparri, A., Priolo, A., & Sukhatme, G. S. (2014). Evaluating network rigidity in realistic systems: Decentralization, asynchronicity, and parallelization. IEEE Transactions on Robotics, 30(4), 950–965.
Xia, N., Ou, Y., Wang, S., Zheng, R., Du, H., et al. (2017). Localizability judgment in uwsns based on skeleton and rigidity theory. IEEE Transactions on Mobile Computing, 1, 1–1.
Zelazo, D., & Mesbahi, M. (2008). On the observability properties of homogeneous and heterogeneous networked dynamic systems. In 2008 47th IEEE conference on decision and control (pp. 2997–3002). https://doi.org/10.1109/CDC.2008.4738920.
Acknowledgements
Authors would like to thank Virginia Tech for engaging classes, continued funding, and access to excellent computation facilities.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Derivation of the observability matrix
Derivation of the observability matrix
As shown in Sect. 3.1 we will need to calculate several successive Lie derivatives in order to get the nonlinear observability matrix. For the following \(i \in [1,N]\), \(j \in [1,d]\), \(\alpha \in [1,A]\), \((u,v) = e_k \in {\mathcal {E}}\), and \((q,r) = e_p \in \mathcal {E^*}\). Let us consider the beacon contribution to the measurement function (7), which gives the following Lie derivatives:
Which we can easily expand on to get the next derivative:
Repeat this process to get the next derivative:
Moving on to the heading measurements, we can evaluate the Lie derivatives associated with these measurements as:
Now replace in next Lie derivative:
Replace once again to get the next:
Finally, we can evaluate the Lie derivatives associated with the range measurement function in a similar way:
Iterate again to get the next order:
Iterate once more to get the following:
Rights and permissions
About this article
Cite this article
Heintzman, L., Williams, R.K. Nonlinear observability of unicycle multi-robot teams subject to nonuniform environmental disturbances. Auton Robot 44, 1149–1166 (2020). https://doi.org/10.1007/s10514-020-09923-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-020-09923-y