Motion planning under uncertainty for robotic tasks with long time horizons
Motion planning under uncertainty for robotic tasks with long time horizons
复制标题
DOI：
10.1177/0278364910386986
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
H. Kurniawati;Yanzhu Du;David Hsu;Wee Sun Lee
中科院分区：
文献类型：
--
作者：
H. Kurniawati;Yanzhu Du;David Hsu;Wee Sun Lee
具有不完美状态信息的运动规划是自主机器人在不确定和动态环境中可靠运行的关键能力。部分可观测马尔可夫决策过程（POMDPs）为不确定性下的规划提供了一个原则性的一般框架。使用概率采样，基于点的POMDP求解器大大提高了POMDP规划的速度，使我们能够处理适度复杂的机器人任务。然而，机器人运动规划任务与长时间的视野仍然是一个严重的障碍，即使是最快的基于点的POMDP求解器今天。本文提出了里程碑引导采样（MiGS），一个新的基于点的POMDP求解器，利用状态空间信息，以减少有效的规划视野。MiGS从机器人的状态空间中采样一组称为里程碑的点，并从采样的里程碑构建状态空间的简化表示。然后，它使用状态空间的这种表示来指导信念空间中的采样，并试图用少量的采样点来捕获信念空间的本质特征。初步结果非常有希望。我们在几个困难的POMDP上进行了模拟测试，这些POMDP在2-D和3-D环境中对不同的机器人任务进行了长时间范围的模拟。这些POMDPs是不可能解决的最快的基于点的求解器今天，但米格在几分钟内解决了他们。
Motion planning with imperfect state information is a crucial capability for autonomous robots to operate reliably in uncertain and dynamic environments. Partially observable Markov decision processes (POMDPs) provide a principled general framework for planning under uncertainty. Using probabilistic sampling, point-based POMDP solvers have drastically improved the speed of POMDP planning, enabling us to handle moderately complex robotic tasks. However, robot motion planning tasks with long time horizons remains a severe obstacle for even the fastest point-based POMDP solvers today. This paper proposes Milestone Guided Sampling (MiGS), a new point-based POMDP solver, which exploits state space information to reduce effective planning horizons. MiGS samples a set of points, called milestones, from a robot’s state space and constructs a simplified representation of the state space from the sampled milestones. It then uses this representation of the state space to guide sampling in the belief space and tries to capture the essential features of the belief space with a small number of sampled points. Preliminary results are very promising. We tested MiGS in simulation on several difficult POMDPs that model distinct robotic tasks with long time horizons in both 2-D and 3-D environments. These POMDPs are impossible to solve with the fastest point-based solvers today, but MiGS solved them in a few minutes.