This paper presents a hybrid online Partially Observable Markov Decision Process (POMDP) planning system that addresses the problem of autonomous navigation in the presence of multi-modal uncertainty introduced by other agents in the environment. As a particular example, we consider the problem of autonomous navigation in dense crowds of pedestrians and among obstacles. Popular approaches to this problem first generate a path using a complete planner (e.g., Hybrid A*) with ad-hoc assumptions about uncertainty, then use online tree-based POMDP solvers to reason about uncertainty with control over a limited aspect of the problem (i.e. speed along the path). We present a more capable and responsive real-time approach enabling the POMDP planner to control more degrees of freedom (e.g., both speed AND heading) to achieve more flexible and efficient solutions. This modification greatly extends the region of the state space that the POMDP planner must reason over, significantly increasing the importance of finding effective roll-out policies within the limited computational budget that real time control affords. Our key insight is to use multi-query motion planning techniques (e.g., Probabilistic Roadmaps or Fast Marching Method) as priors for rapidly generating efficient roll-out policies for every state that the POMDP planning tree might reach during its limited horizon search. Our proposed approach generates trajectories that are safe and significantly more efficient than the previous approach, even in densely crowded dynamic environments with long planning horizons.
翻译:本文介绍了一个混合的在线部分可观测的Markov Markov 决策程序(POMDP)规划系统(POMDP),该规划系统在环境中其他代理人引入多模式不确定性的情况下解决自主导航问题。作为一个特别的例子,我们考虑了在密集行人人群和障碍中自主导航的问题。这个问题的大众化方法首先产生一条路径,使用完整的规划器(如混合A* ),并附带对不确定性的假设,然后使用基于在线树的POMDP 解决方案,以解释不确定性,并控制问题的一个有限方面(即沿路速度)。我们提出了一个更有能力和反应迅速的实时方法,使POMDP 规划器能够控制更多程度的自由(如速度和航向),从而实现更灵活和高效的解决办法。这一修改极大地扩大了POMDP 规划师必须理解的州空间范围,从而大大提高了在有限计算预算范围内找到有效的推出政策的重要性,而实际时间控制是有限的。我们的关键洞察力是使用多动规划技术(例如:快速规划技术,快速和快速规划,在前期马氏路线图期间可能大大推进之前的快速搜索。