Reasoning and predicting POMDP planning complexity via covering numbers

Partially observable Markov decision processes (POMDPs) provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l ₁-metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the l _n-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.     

Planning for multiple measurement channels in a continuous-state POMDP

Continuous-state partially observable Markov decision processes (POMDPs) are an intuitive choice of representation for many stochastic planning problems with a hidden state. We consider a continuous-state POMDPs with finite action and observation spaces, where the POMDP is parametrised by weighted sums of Gaussians, or Gaussian mixture models (GMMs). In particular, we study the problem of optimising the selection of measurement channel in such a framework. A new error bound for a point-based value iteration algorithm is derived, and a method for constructing a subset of belief states that attempts to reduce the error bound is implemented. In the experiments, applying continuous-state POMDPs for optimal selection of the measurement channel is demonstrated, and the performance of three GMM simplification methods is compared. Convergence of a point-based value iteration algorithm is investigated by considering various metrics for the obtained control policies.     

Scaling POMDPs for Spoken Dialog Management

Control in spoken dialog systems is challenging largely because automatic speech recognition is unreliable, and hence the state of the conversation can never be known with certainty. Partially observable Markov decision processes (POMDPs) provide a principled mathematical framework for planning and control in this context; however, POMDPs face severe scalability challenges, and past work has been limited to trivially small dialog tasks. This paper presents a novel POMDP optimization technique-composite summary point-based value iteration (CSPBVI)-which enables optimization to be performed on slot-filling POMDP-based dialog managers of a realistic size. Using dialog models trained on data from a tourist information domain, simulation results show that CSPBVI scales effectively, outperforms non-POMDP baselines, and is robust to estimation errors.     

Real-time hierarchical POMDPs for autonomous robot navigation

This paper proposes a new hierarchical formulation of POMDPs for autonomous robot navigation that can be solved in real-time, and is memory efficient. It will be referred to in this paper as the Robot Navigation–Hierarchical POMDP (RN-HPOMDP). The RN-HPOMDP is utilized as a unified framework for autonomous robot navigation in dynamic environments. As such, it is used for localization, planning and local obstacle avoidance. Hence, the RN-HPOMDP decides at each time step the actions the robot should execute, without the intervention of any other external module for obstacle avoidance or localization. Our approach employs state space and action space hierarchy, and can effectively model large environments at a fine resolution. Finally, the notion of the reference POMDP is introduced. The latter holds all the information regarding motion and sensor uncertainty, which makes the proposed hierarchical structure memory efficient and enables fast learning. The RN-HPOMDP has been experimentally validated in real dynamic environments.     

Planning in partially-observable switching-mode continuous domains

Continuous-state POMDPs provide a natural representation for a variety of tasks, including many in robotics. However, most existing parametric continuous-state POMDP approaches are limited by their reliance on a single linear model to represent the world dynamics. We introduce a new switching-state dynamics model that can represent multi-modal state-dependent dynamics. We present the Switching Mode POMDP (SM-POMDP) planning algorithm for solving continuous-state POMDPs using this dynamics model. We also consider several procedures to approximate the value function as a mixture of a bounded number of Gaussians. Unlike the majority of prior work on approximate continuous-state POMDP planners, we provide a formal analysis of our SM-POMDP algorithm, providing bounds, where possible, on the quality of the resulting solution. We also analyze the computational complexity of SM-POMDP. Empirical results on an unmanned aerial vehicle collisions avoidance simulation, and a robot navigation simulation where the robot has faulty actuators, demonstrate the benefit of SM-POMDP over a prior parametric approach.     

Exploiting submodular value functions for scaling up active perception

In active perception tasks, an agent aims to select sensory actions that reduce its uncertainty about one or more hidden variables. For example, a mobile robot takes sensory actions to efficiently navigate in a new environment. While partially observable Markov decision processes (POMDPs) provide a natural model for such problems, reward functions that directly penalize uncertainty in the agent’s belief can remove the piecewise-linear and convex (PWLC) property of the value function required by most POMDP planners. Furthermore, as the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially with it, making POMDP planning infeasible with traditional methods. In this article, we address a twofold challenge of modeling and planning for active perception tasks. We analyze \(\rho \)POMDP and POMDP-IR, two frameworks for modeling active perception tasks, that restore the PWLC property of the value function. We show the mathematical equivalence of these two frameworks by showing that given a \(\rho \)POMDP along with a policy, they can be reduced to a POMDP-IR and an equivalent policy (and vice-versa). We prove that the value function for the given \(\rho \)POMDP (and the given policy) and the reduced POMDP-IR (and the reduced policy) is the same. To efficiently plan for active perception tasks, we identify and exploit the independence properties of POMDP-IR to reduce the computational cost of solving POMDP-IR (and \(\rho \)POMDP). We propose greedy point-based value iteration (PBVI), a new POMDP planning method that uses greedy maximization to greatly improve scalability in the action space of an active perception POMDP. Furthermore, we show that, under certain conditions, including submodularity, the value function computed using greedy PBVI is guaranteed to have bounded error with respect to the optimal value function. We establish the conditions under which the value function of an active perception POMDP is guaranteed to be submodular. Finally, we present a detailed empirical analysis on a dataset collected from a multi-camera tracking system employed in a shopping mall. Our method achieves similar performance to existing methods but at a fraction of the computational cost leading to better scalability for solving active perception tasks.     

Probabilistic Road Map sampling strategies for multi-robot motion planning

This paper presents a Probabilistic Road Map (PRM) motion planning algorithm to be queried within Dynamic Robot Networks—a multi-robot coordination platform for robots operating with limited sensing and inter-robot communication.

First, the Dynamic Robot Networks (DRN) coordination platform is introduced that facilitates centralized robot coordination across ad hoc networks, allowing safe navigation in dynamic, unknown environments. As robots move about their environment, they dynamically form communication networks. Within these networks, robots can share local sensing information and coordinate the actions of all robots in the network.

Second, a fast single-query Probabilistic Road Map (PRM) to be called within the DRN platform is presented that has been augmented with new sampling strategies. Traditional PRM strategies have shown success in searching large configuration spaces. Considered here is their application to on-line, centralized, multiple mobile robot planning problems. New sampling strategies that exploit the kinematics of non-holonomic mobile robots have been developed and implemented. First, an appropriate method of selecting milestones in a PRM is identified to enable fast coverage of the configuration space. Second, a new method of generating PRM milestones is described that decreases the planning time over traditional methods. Finally, a new endgame region for multi-robot PRMs is presented that increases the likelihood of finding solutions given difficult goal configurations.

Combining the DRN platform with these new sampling strategies, on-line centralized multi-robot planning is enabled. This allows robots to navigate safely in environments that are both dynamic and unknown. Simulations and real robot experiments are presented that demonstrate: (1) speed improvements accomplished by the sampling strategies, (2) centralized robot coordination across Dynamic Robot Networks, (3) on-the-fly motion planning to avoid moving and previously unknown obstacles and (4) autonomous robot navigation towards individual goal locations.     

Planning to see: A hierarchical approach to planning visual actions on a robot using POMDPs

Flexible, general-purpose robots need to autonomously tailor their sensing and information processing to the task at hand. We pose this challenge as the task of planning under uncertainty. In our domain, the goal is to plan a sequence of visual operators to apply on regions of interest (ROIs) in images of a scene, so that a human and a robot can jointly manipulate and converse about objects on a tabletop. We pose visual processing management as an instance of probabilistic sequential decision making, and specifically as a Partially Observable Markov Decision Process (POMDP). The POMDP formulation uses models that quantitatively capture the unreliability of the operators and enable a robot to reason precisely about the trade-offs between plan reliability and plan execution time. Since planning in practical-sized POMDPs is intractable, we partially ameliorate this intractability for visual processing by defining a novel hierarchical POMDP based on the cognitive requirements of the corresponding planning task. We compare our hierarchical POMDP planning system (HiPPo) with a non-hierarchical POMDP formulation and the Continual Planning (CP) framework that handles uncertainty in a qualitative manner. We show empirically that HiPPo and CP outperform the naive application of all visual operators on all ROIs. The key result is that the POMDP methods produce more robust plans than CP or the naive visual processing. In summary, visual processing problems represent a challenging domain for planning techniques and our hierarchical POMDP-based approach for visual processing management opens up a promising new line of research.     

The Skyline algorithm for POMDP value function pruning

We address the pruning or filtering problem, encountered in exact value iteration in POMDPs and elsewhere, in which a collection of linear functions is reduced to the minimal subset retaining the same maximal surface. We introduce the Skyline algorithm, which traces the graph corresponding to the maximal surface. The algorithm has both a complete and an iterative version, which we present, along with the classical Lark??s algorithm, in terms of the basic dictionary-based simplex iteration from linear programming. We discuss computational complexity results, and present comparative experiments on both randomly-generated and well-known POMDP benchmarks.     

基于采样的POMDP近似算法

部分可观察马尔科夫决策过程（POMDP）是一种描述机器人在动态不确定环境下行动选择的问题模型。对于具有稀疏转移矩阵的POMDP问题模型，该文提出了一种求解该问题模型的快速近似算法。该算法首先利用QMDP算法产生的策略进行信念空间采样，并通过点迭代算法快速生成POMDP值函数，从而产生近似的最优行动选择策略。在相同的POMDP试验模型上，执行该算法产生的策略得到的回报值与执行其他近似算法产生的策略得到的回报值相当，但该算法计算速度快，它产生的策略表示向量集合小于现有其他近似算法产生的集合。因此，它比这些近似算法更适应于大规模的稀疏状态转移矩阵POMDP模型求解计算。     

What is decidable about partially observable Markov decision processes with ω-regular objectives

We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.     

Step sequence planning for a biped robot by means of a cylindrical shape model and a high-resolution 2.5D map

A novel step sequence planning (SSP) method for biped-walking robots is presented. The method adopts a free space representation custom-designed for efficient biped robot motion planning. The method rests upon the approximation of the robot shape by a set of 3D cylindrical solids. This feature allows efficient determination of feasible paths in a 2.5D map, comprising stepping over obstacles and stair climbing. A SSP algorithm based on A^∗-search is proposed which uses the advantages of the aforementioned environment representation. The efficiency of the proposed approach is evaluated by a series of simulations performed for eight walking scenarios.     

Robot formation motion planning using Fast Marching

This paper presents the application of the Voronoi Fast Marching (VFM) method to path planning of mobile formation robots. The VFM method uses the propagation of a wave (Fast Marching) operating on the world model to determine a motion plan over a viscosity map (similar to the refraction index in optics) extracted from the updated map model. The computational efficiency of the method allows the planner to operate at high rate sensor frequencies. This method allows us to maintain good response time and smooth and safe planned trajectories. The navigation function can be classified as a type of potential field, but it has no local minima, it is complete (it finds the solution path if it exists) and it has a complexity of order n(O(n)), where n is the number of cells in the environment map. The results presented in this paper show how the proposed method behaves with mobile robot formations and generates trajectories of good quality without problems of local minima when the formation encounters non-convex obstacles.     

Motion strategies for exploration and map building under uncertainty with multiple heterogeneous robots

In this paper, we present a multi-robot exploration strategy for map building. We consider an indoor structured environment and a team of robots with different sensing and motion capabilities. We combine geometric and probabilistic reasoning to propose a solution to our problem. We formalize the proposed solution using stochastic dynamic programming (SDP) in states with imperfect information. Our modeling can be considered as a partially observable Markov decision process (POMDP), which is optimized using SDP. We apply the dynamic programming technique in a reduced search space that allows us to incrementally explore the environment. We propose realistic sensor models and provide a method to compute the probability of the next observation given the current state of the team of robots based on a Bayesian approach. We also propose a probabilistic motion model, which allows us to take into account errors (noise) on the velocities applied to each robot. This modeling also allows us to simulate imperfect robot motions, and to estimate the probability of reaching the next state given the current state. We have implemented all our algorithms and simulations results are presented.     

An efficient algorithm for one-step planar compliant motion planning with uncertainty

Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give anO(n ² logn) algorithm to find a single commanded motion direction that will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.     

VCS-based motion planning for distributed mobile robots: collision avoidance and formation

This paper addresses decentralized motion planning among a homogeneous set of feedback-controlled mobile robots. It introduces the velocity obstacle, which describes the collision between robot and obstacle, and the hybrid interactive velocity obstacles are designed for collision checking between interacting robots. The (sub)goal selection algorithm is also studied for formation control, then the preferred velocity is designed for robot tracking its desired (sub)goal. Furthermore, the rules for the size regulation of obstacle are presented to avoid conservative motion planning and enhance the safety. Then, we establish a novel Velocity Change Space (VCS), map the velocity obstacles, the desired (sub)goal and the reachable velocity change window before collision in this space, and directly get the new velocity by a multi-objective optimization method. We apply VCS-based motion planning methods to distributed robots, and simulation is used to illustrate the good performances with respect to the un-conservative, foresighted and multi-objective optimal motion planning, especially the successful application in the formation control of the multi-robot system.     

B-spline wavelet-based motion smoothing

A B-spline wavelet-based algorithm is proposed in this study to solve the motion smoothing problem, which has practical applications in the computer animation and virtual reality (VR) areas. The motion of a rigid body consists of translation and rotation. The former is described by a space curve in three-dimensional Euclidean space, while the latter is represented by a curve in the unit quaternion space. Due to the complexity of rendering realistic rigid-body motions in the computer, rigid-body motions are often sampled from the physical world motions. Yet, sampling processes introduce noise; excessive noise results in tremulous motions in a VR environment. The noise-embedded motion data are decomposed using multiresolution analysis and the noise is detected as components of small magnitude. By eliminating the small-magnitude components, a smooth representation of the motion data is achieved.     

Collision-free motion planning of dual-arm reconfigurable robots

Dual-arm reconfigurable robot is a new type of robot. It can adapt to different tasks by changing its different end-effector modules which have standard connectors. Especially, in fast and flexible assembly, it is very important to research the collision-free planning of dual-arm reconfigurable robots. It is to find a continuous, collision-free path in an environment containing obstacles. A new approach to the real-time collision-free motion planning of dual-arm reconfigurable robots is used in the paper. This method is based on configuration space (C-Space). The method of configuration space and the concepts reachable manifold and contact manifold are successfully applied to the collision-free motion planning of dual-arm robot. The complexity of dual-arm robots’ collision-free planning will reduce to a search in a dispersed C-Space. With this algorithm, a real-time optimum path is found. And when the start point and the end point of the dual-arm robot are specified, the algorithm will successfully get the collision-free path real time. A verification of this algorithm is made in the dual-arm horizontal articulated robot SCARATES, and the simulation and experiment ascertain that the algorithm is feasible and effective.     

Safe and efficient motion planning of multiple mobile robots based on artificial potential for human behavior and robot congestion

In order for robots to exist together with humans, safety for the humans has to be strictly ensured. On the other hand, safety might decrease working efficiency of robots. Namely, this is a trade-off problem between human safety and robot efficiency in a field of human–robot interaction. For this problem, we propose a novel motion planning technique of multiple mobile robots. Two artificial potentials are presented for generating repulsive force. The first potential is provided for humans. The von Mises distribution is used to consider the behavioral property of humans. The second potential is provided for the robots. The Kernel density estimation is used to consider the global robot congestion. Through simulation experiments, the effectiveness of the behavior and congestion potentials of the motion planning technique for human safety and robot efficiency is discussed. Moreover, a sensing system for humans in a real environment is developed. From experimental results, the significance of the behavior potential based on the actual humans is discussed. For the coexistence of humans and robots, it is important to evaluate a mutual influence between them. For this purpose, a virtual space is built using projection mapping. Finally, the effectiveness of the motion planning technique for the human–robot interaction is discussed from the point of view of not only robots but also humans.     

表征空间中的机器人分层运动规划

由于对机器人的任务要求日趋复杂和多变,如何使机器人具备灵活的配置和运动规划能力,以适应复杂任务的需求,成为了目前运动规划领域所研究的核心问题.传统的基于任务空间和配置空间的建模方法虽然在机器人运动规划领域得到了非常广泛的应用,但在用于解决复杂规划任务时无法对不可行任务进行进一步地处理.本文在表征空间模型的基础上,提出了一种分层的运动规划算法,一方面借助于表征空间维度的扩展,使对运动规划任务的描述更为灵活;另一方面通过任务层与运动层的循环交互,使生成的路径满足更高层次和更丰富的任务要求.在仿人机器人和多机器人系统上的应用结果表明了本文所提算法的有效性.