HyP-DESPOT: A Hybrid Parallel Algorithm for Online Planning under Uncertainty
Planning under uncertainty is critical for robust robot performance in uncertain, dynamic environments, but it incurs high computational cost. State-of-the-art online search algorithms, such as DESPOT, have vastly improved the computational efficiency of planning under uncertainty and made it a valuable tool for robotics in practice. This work takes one step further by leveraging both CPU and GPU parallelization in order to achieve near real-time online planning performance for complex tasks with large state, action, and observation spaces. Specifically, we propose Hybrid Parallel DESPOT (HyP-DESPOT), a massively parallel online planning algorithm that integrates CPU and GPU parallelism in a multi-level scheme. It performs parallel DESPOT tree search by simultaneously traversing multiple independent paths using multi-core CPUs and performs parallel Monte-Carlo simulations at the leaf nodes of the search tree using GPUs. Experimental results show that HyP-DESPOT speeds up online planning by up to several hundred times, compared with the original DESPOT algorithm, in several challenging robotic tasks in simulation.
Code (1)
Tasks
Computational EfficiencyCPUGPUSimilar Papers 제목 키워드 기반
DESPOT: Online POMDP Planning with Regularization
The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the "curse of dimension…
Autonomous DrivingCAR-DESPOT: Causally-Informed Online POMDP Planning for Robots in Confounded Environments
Robots operating in real-world environments must reason about possible outcomes of stochastic actions and make decisions based on partial observations of the true world state. A major challenge for making accurate and ro…
Decision MakingCan justice be fair when it is blind? How social network structures can promote or prevent the evolution of despotism
Hierarchy is an efficient way for a group to organize, but often goes along with inequality that benefits leaders. To control despotic behaviour, followers can assess leaders decisions by aggregating their own and their …
Scalable Planning with Tensorflow for Hybrid Nonlinear Domains
Given recent deep learning results that demonstrate the ability to effectively optimize high-dimensional non-convex functions with gradient descent optimization on GPUs, we ask in this paper whether symbolic gradient opt…
Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach
Partially Observable Markov Decision Processes (POMDPs) are a powerful framework for planning under uncertainty. They allow to model state uncertainty as a belief probability distribution. Approximate solvers based on Mo…
Inductive logic programming