Abstract
In this paper we develop a novel paradigm to efficiently solve decision making and planning problems, and demonstrate it for the challenging case of planning under uncertainty. While conventional methods tend to optimize properties of specific problems, and sacrifice performance in order to reduce their complexity, our approach has no coupling to a specific problem, and relies solely on the structure of the general decision problem, in order to directly reduce its computational cost, with no influence over the quality of solution, nor the maintained state. Using bounded approximations of the state, we can easily eliminate unfit actions, while sparing the need to exactly evaluate the objective function for all the candidate actions. The original problem can then be solved considering a minimal subset of candidates. Since the approach is especially relevant when the action domain is large, and the objective function is expensive to evaluate, we later extend the discussion specifically for decision making under uncertainty and belief space planning, and present dedicated and practical tools, in order to apply the method to a sensor deployment problem. This paper continues our previous work towards efficient decision making.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Elimelech, K., Indelman, V.: Consistent sparsification for efficient decision making under uncertainty in high dimensional state spaces. In: IEEE International Conference on Robotics and Automation (ICRA) (2017)
Elimelech, K., Indelman, V.: Scalable sparsification for efficient decision making under uncertainty in high dimensional state spaces. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2017)
Indelman, V.: No correlations involved: decision making under uncertainty in a conservative sparse information space. IEEE Robot. Autom. Lett. (RA-L) 1(1), 407–414 (2016)
He, R., Prentice, S., Roy, N.: Planning in information space for a quadrotor helicopter in a gps-denied environment. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 1814–1820 (2008)
Huang, G., Kaess, M., Leonard, J.J.: Consistent sparsification for graph optimization. In: Proceedings of the European Conference on Mobile Robots (ECMR), pp. 150–157 (2012)
Carlevaris-Bianco, N., Kaess, M., Eustice, R.M.: Generic node removal for factor-graph SLAM. IEEE Trans. Robot. 30(6), 1371–1385 (2014)
Roy, N., Gordon, G., Thrun, S.: Finding approximate pomdp solutions through belief compression. J. Artif. Intell. Res. 23, 1–40 (2005)
Patil, S., Kahn, G., Laskey, M., Schulman, J., Goldberg, K., Abbeel, P.: Scaling up gaussian belief space planning through covariance-free trajectory optimization and automatic differentiation. In International Workshop on the Algorithmic Foundations of Robotics (2014)
Indelman, V., Carlone, L., Dellaert, F.: 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)
Eustice, R., Walter, M., Leonard, J.: Sparse extended information filters: insights into sparsification. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3281–3288, Aug 2005
Prentice, S., Roy, N.: The belief roadmap: efficient planning in belief space by factoring the covariance. Int. J. Robot. Res. (2009)
Van Den Berg, J., Abbeel, P., Goldberg, K.: Lqg-mp: optimized path planning for robots with motion uncertainty and imperfect state information. Intl. J. Robot. Res. 30(7), 895–913 (2011)
Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008)
Platt, R., Tedrake, R., Kaelbling, L.P., Lozano-Pérez, T.: Belief space planning assuming maximum likelihood observations. In: Robotics: Science and Systems (RSS), Zaragoza, Spain, pp. 587–593 (2010)
Nakhost, H., Müller, M.: Action elimination and plan neighborhood graph search: two algorithms for plan improvement. In: Twentieth International Conference on Automated Planning and Scheduling (ICAPS), pp. 121–128 (2010)
Rosman, B., Ramamoorthy, S.: What good are actions? Accelerating learning using learned action priors. In: 2012 IEEE International Conference on Development and Learning and Epigenetic Robotics (ICDL), pp. 1–6. IEEE (2012)
Sherstov, A., Stone, P.: Action-space knowledge transfer in mdps: Formalism, suboptimality bounds, and algorithms. In: Conference on Learning Theory (2005)
Abel, D., Hershkowitz, D.E., Barth-Maron, G., Brawner, S., O’Farrell, K., MacGlashan, J., Tellex, S.: Goal-based action priors. In: Twenty-Fifth International Conference on Automated Planning and Scheduling(ICAPS), pp. 306–314 (2015)
Kuter, U., Hu, J.: Computing and using lower and upper bounds for action elimination in mdp planning. In: International Symposium on Abstraction, Reformulation, and Approximation, pp. 243–257. Springer, Heidelberg (2007)
Even-Dar, E., Mannor, S., Mansour, Y.: Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res. 7(Jun), 1079–1105 (2006)
Bry, A., Roy, N.: Rapidly-exploring random belief trees for motion planning under uncertainty. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 723–730 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Elimelech, K., Indelman, V. (2020). Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations. In: Amato, N., Hager, G., Thomas, S., Torres-Torriti, M. (eds) Robotics Research. Springer Proceedings in Advanced Robotics, vol 10. Springer, Cham. https://doi.org/10.1007/978-3-030-28619-4_58
Download citation
DOI: https://doi.org/10.1007/978-3-030-28619-4_58
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-28618-7
Online ISBN: 978-3-030-28619-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)