Abstract
This paper presents a method that allows mobile systems with uncertainty in motion and sensing to react to unknown environments while high-level specifications are satisfied. Although previous works have addressed the problem of synthesising controllers under uncertainty constraints and temporal logic specifications, reaction to dynamic environments has not been considered under this scenario. The method uses feedback-based information roadmaps (FIRMs) to break the curse of history associated with partially observable systems. A transition system is incrementally constructed based on the idea of FIRMs by adding nodes on the belief space. Then, a policy is found in the product Markov decision process created between the transition system and a Rabin automaton representing a linear temporal logic formula. The proposed solution allows the system to react to previously unknown elements in the environment. To achieve fast reaction time, a FIRM considering the probability of violating the specification in each transition is used to drive the system towards local targets or to avoid obstacles. The method is demonstrated with an illustrative example.
Felipe J. Montana is supported by the Mexican National Council of Science and Technology (CONACyT). Jun Liu is supported in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada and the Canada Research Chairs (CRC) program.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agha-Mohammadi, A.A., Chakravorty, S., Amato, N.M.: FIRM: sampling-based feedback motion-planning under motion uncertainty and imperfect measurements. Int. J. Robot. Res. 33(2), 268–304 (2014)
Ayala, A.M., Andersson, S.B., Belta, C.: Temporal logic motion planning in unknown environments. In: Proceedings of IROS, pp. 5279–5284. IEEE (2013)
Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press, Cambridge (2008)
Bauer, A., Leucker, M., Schallhart, C.: Runtime verification for LTL and TLTL. In: Proceedings of FSTTCS, vol. 20, pp. 1–68. ACM (2006)
Bry, A., Roy, N.: Rapidly-exploring random belief trees for motion planning under uncertainty. In: Proceedings of ICRA, pp. 723–730. IEEE (2011)
Chatterjee, K., Chmelík, M., Gupta, R., Kanodia, A.: Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. In: Procedings of ICRA, pp. 325–330. IEEE (2015)
Cormen, T.H.: Introduction to Algorithms. MIT press, Cambridge (2009)
Fu, J., Topcu, U.: Integrating active sensing into reactive synthesis with temporal logic constraints under partial observations. In: Proceedings of ACC, pp. 2408–2413. IEEE (2015)
Horowitz, M.B., Wolff, E.M., Murray, R.M.: A compositional approach to stochastic optimal control with co-safe temporal logic specifications. In: Proceedings of IROS, pp. 1466–1473. IEEE (2014)
Kallman, M., Mataric, M.: Motion planning using dynamic roadmaps. In: Proceedings of ICRA, vol. 5, pp. 4399–4404. IEEE (2004)
Karaman, S., Frazzoli, E.: Sampling-based motion planning with deterministic \(\mu \)-calculus specifications. In: Proceedings of CDC/CCC, pp. 2222–2229. IEEE (2009)
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
Leven, P., Hutchinson, S.: Toward real-time path planning in changing environments. In: Algorithmic and Computational Robotics: New Directions, pp. 363–376. A K Peters (2000)
Littman, M.L., Dean, T.L., Kaelbling, L.P.: On the complexity of solvingMarkov decision problems. In: Proceedings of UAI, pp. 394–402. Morgan Kaufmann Publishers Inc. (1995)
Montana, F.J., Liu, J., Dodd, T.J.: Sampling-based stochastic optimal control with metric interval temporal logic specifications. In: Proceedings of CCA, pp. 767–773. IEEE (2016)
Pineau, J., Gordon, G., Thrun, S., et al.: Point-based value iteration: An anytime algorithm for POMDPs. In: Proceedings of IJCAI, vol. 3, pp. 1025–1032 (2003)
Prentice, S., Roy, N.: The belief roadmap: efficient planning in linear POMDPs by factoring the covariance. In: Kaneko, M., Nakamura, Y. (eds.) Robotics Research, pp. 293–305. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14743-2_25
Svoreňová, M., Chmelík, M., Leahy, K., Eniser, H.F., Chatterjee, K., Černá, I., Belta, C.: Temporal logic motion planning using POMDPs with parity objectives: case study paper. In: Proceedings of HSCC, pp. 233–238. ACM (2015)
Vasile, C.I., Belta, C.: Reactive sampling-based temporal logic path planning. In: Proceedings of ICRA, pp. 4310–4315. IEEE (2014)
Vasile, C.I., Leahy, K., Cristofalo, E., Jones, A., Schwager, M., Belta, C.: Control in belief space with temporal logic specifications. In: Proceedings of CDC, pp. 7419–7424. IEEE (2016)
Wongpiromsarn, T., Frazzoli, E.: Control of probabilistic systems under dynamic, partially known environments with temporal logic specifications. In: Proceedings of CDC, pp. 7644–7651. IEEE (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Montana, F.J., Liu, J., Dodd, T.J. (2017). Sampling-Based Reactive Motion Planning with Temporal Logic Constraints and Imperfect State Information. In: Petrucci, L., Seceleanu, C., Cavalcanti, A. (eds) Critical Systems: Formal Methods and Automated Verification. AVoCS FMICS 2017 2017. Lecture Notes in Computer Science(), vol 10471. Springer, Cham. https://doi.org/10.1007/978-3-319-67113-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-67113-0_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67112-3
Online ISBN: 978-3-319-67113-0
eBook Packages: Computer ScienceComputer Science (R0)