This paper proposes Partially Observable Reference Policy Programming, a novel anytime online approximate POMDP solver which samples meaningful future histories very deeply while simultaneously forcing a gradual policy update. We provide theoretical guarantees for the algorithm’s underlying scheme which say that the performance loss is bounded by the average of the sampling approximation errors rather than the usual maximum; a crucial requirement given the sampling sparsity of online planning. Empirical evaluations on two large-scale problems with dynamically evolving environments—including a helicopter emergency scenario in the Corsica region requiring approximately 150 planning steps—corroborate the theoretical results and indicate that our solver considerably outperforms current online benchmarks.

The aging and increasing complexity of infrastructures make efficient inspection planning more critical in ensuring safety. Thanks to sampling-based motion planning, many inspection planners are fast. However, they often require huge memory. This is particularly true when the structure under inspection is large and complex, consisting of many struts and pillars of various geometry and sizes. Such structures can be represented efficiently using implicit models, such as neural Signed Distance Functions (SDFs). However, most primitive computations used in sampling-based inspection planner have been designed to work efficiently with explicit environment models, which in turn requires the planner to use explicit environment models or performs frequent transformations between implicit and explicit environment models during planning. This paper proposes a set of primitive computations, called Inspection Planning Primitives with Implicit Models (IPIM), that enable sampling-based inspection planners to entirely use neural SDFs representation during planning. Evaluation on three scenarios, including inspection of a complex real-world structure with over 92M triangular mesh faces, indicates that even a rudimentary sampling-based planner with IPIM can generate inspection trajectories of similar quality to those generated by the state-of-the-art planner, while using up to 70× less memory than the state-of-the-art inspection planner.

Abstract Seamless integration of Planning Under Uncertainty and Reinforcement Learning (RL) promises to bring the best of both model-driven and data-driven worlds to multi-agent decision-making, resulting in an approach with assurances on performance that scales well to more complex problems. Despite this potential, progress in developing such methods has been hindered by the lack of adequate evaluation and simulation platforms. Researchers have had to rely on creating custom environments, which reduces efficiency and makes comparing new methods difficult. In this paper, we introduce POSGGym : a library for facilitating planning and RL research in partially observable, multi-agent domains. It provides a diverse collection of discrete and continuous environments, complete with their dynamics models and a reference set of policies that can be used to evaluate generalization to novel co-players. Leveraging POSGGym, we empirically investigate existing state-of-the-art planning methods and a method that combines planning and RL in the type-based reasoning setting. Our experiments corroborate that combining planning and RL can yield superior performance compared to planning or RL alone, given the model of the environment and other agents is correct. However, our particular setup also reveals that this integrated approach could result in worse performance when the model of other agents is incorrect. Our findings indicate the benefit of integrating planning and RL in partially observable, multi-agent domains, while serving to highlight several important directions for future research. Code available at: https://github.com/RDLLab/posggym .

Abstract Fisheries, as indispensable natural resources for human, need to be managed with both short‐term economical benefits and long‐term sustainability in consideration. This has remained a challenge, because the population and catch dynamics of the fisheries are complex and noisy, while the data available is often scarce and only provides partial information on the dynamics. To address these challenges, we formulate the population and catch dynamics as a Partially Observable Markov Decision Process (POMDP), and propose a model‐based offline reinforcement learning approach to learn an optimal management policy. Our approach allows learning fishery management policies from possibly incomplete fishery data generated by a stochastic fishery system. This involves first learning a POMDP fishery model using a novel least squares approach, and then computing the optimal policy for the learned POMDP. The learned fishery dynamics model is useful for explaining the resulting policy's performance. We perform systematic and comprehensive simulation study to quantify the effects of stochasticity in fishery dynamics, proliferation rates, missing values in fishery data, dynamics model misspecification, and variability of effort (e.g., the number of boat days). When the effort is sufficiently variable and the noise is moderate, our method can produce a competitive policy that achieves 85% of the optimal value, even for the hardest case of noisy incomplete data and a misspecified model. Interestingly, the learned policies seem to be robust in the presence of model learning errors. However, non‐identifiability kicks in if there is insufficient variability in the effort level and the fishery system is stochastic. This often results in poor policies, highlighting the need for sufficiently informative data. We also provide a theoretical analysis on model misspecification and discuss the tendency of a Schaefer model to overfit compared with a Beverton–Holt model.

The Partially Observable Markov Decision Process (POMDP) provides a principled framework for decision making in stochastic partially observable environments. However, computing good solutions for problems with continuous action spaces remains challenging. To ease this challenge, we propose a simple online POMDP solver, called Lazy Cross-Entropy Search Over Policy Trees (LCEOPT). At each planning step, our method uses a novel lazy Cross-Entropy method to search the space of policy trees, which provide a simple policy representation. Specifically, we maintain a distribution on promising finite-horizon policy trees. The distribution is iteratively updated by sampling policies, evaluating them via Monte Carlo simulation, and refitting them to the top-performing ones. Our method is lazy in the sense that it exploits the policy tree representation to avoid redundant computations in policy sampling, evaluation, and distribution update. This leads to computational savings of up to two orders of magnitude. Our LCEOPT is surprisingly simple as compared to existing state-of-the-art methods, yet empirically outperforms them on several continuous-action POMDP problems, particularly for problems with higher-dimensional action spaces.

Motion planning is a fundamental capability in robotics applications. Real-world scenarios can introduce uncertainty to the motion planning problem. In this work we study environment uncertainty in general high-dimensional problems wherein the choice of appropriate metrics and formulations are shown to have significant effect on the probability of collision of the solution path. Several practically motivated cost functions have been proposed in literature to model and solve the problem but are shown in this work to suffer from higher probabilities of collision. The current work presents a theoretically sound formulation that was first mentioned in previous work on minimum constraint removal. In this work, approximating the optimal problem is shown to be better in achieving lower probability of collision. To demonstrate the formulation in a sampling-based setting, a mixed integer linear program seeded by greedy search over a roadmap with sampled environments is used to report paths with low probability of collision. Compared against minimizing the sum and minimizing max probability cost functions on a seven degree-of-freedom robotic arm in uncertain environments, we show clear benefits and promise towards motion planning for optimal probability of collision.

Many planning problems in robotics require long planning horizon and uncertain in nature. The Par-tially Observable Markov Descision Process (POMDP) is a mathematically principled framework for planning under uncertainty. To alleviate the difficulties of computing good approximate POMDP solutions for long horizon problems, one often plans using macro actions, where each macro action is a chain of primitive actions. Such a strategy reduces the effective planning horizon of the problem, and hence reduces the computational complexity for solving. The difficulty is in generating a set of suitable macro actions. In this paper, we present a simple recurrent neural network that learns to generate suitable sets of candidate macro actions that exploits environment information. Key to this learning method is to represent the raw partial information from the environment as a latent problem instance, and sequentially generate macro actions conditioned on the past information. We compare our proposed method with state-of-the-art [1] on four dif-ferent long horizon planning tasks with various difficulties. The results indicate the quality of the policies computed using macro actions generated by our proposed method consistently exceeds benchmarks. Our implementation can be accessed at https://github.com/YC-Liang/Recurrent-Macro-Action-Generator.

Efficiently searching for target objects in complex environments that contain various types of furniture, such as shelves, tables, and beds, is crucial for mobile robots, but it poses significant challenges due to various factors such as localization errors, limited field of view, and visual occlusion. To address this problem, we propose a Partially Observable Markov Decision Process (POMDP) formulation with a growing state space for object search in a 3D region. We solve this POMDP by carefully designing a perception module and developing a planning algorithm, called Growing Partially Observable Monte-Carlo Planning (GPOMCP), based on online Monte-Carlo tree search and belief tree reuse with a novel upper confidence bound. We have demonstrated that belief tree reuse is reasonable and achieves good performance when the belief differences are limited. Additionally, we introduce a guessed target object with an updating grid world to guide the search in the information-less and reward-less cases, like the absence of any detected objects. We tested our approach using Gazebo simulations on four scenarios of target finding in a realistic indoor living environment with the Fetch robot simulator. Compared to the baseline approaches, which are based on POMCP, our results indicate that our approach enables the robot to find the target object with a higher success rate faster while using the same computational requirements.

Making good decisions in partially observable and non-deterministic scenarios is a crucial capability for robots. A Partially Observable Markov Decision Process (POMDP) is a general framework for the above problem. Despite advances in POMDP solving, problems with long planning horizons and evolving environments remain difficult to solve even by the best approximate solvers today. To alleviate this difficulty, we propose a slightly modified POMDP problem, called a Reference-Based POMDP, where the objective is to balance between maximizing the expected total reward and being close to a given reference (stochastic) policy. The optimal policy of a Reference-Based POMDP can be computed via iterative expectations using the given reference policy, thereby avoiding exhaustive enumeration of actions at each belief node of the search tree. We demonstrate theoretically that the standard POMDP under stochastic policies is related to the Reference-Based POMDP. To demonstrate the feasibility of exploiting the formulation, we present a basic algorithm RefSolver. Results from experiments on long-horizon navigation problems indicate that this basic algorithm substantially outperforms POMCP.

The ability to make good decisions in partially observed non-cooperative multi-agent scenarios is important for robots to interact effectively in human environments. A robust framework for such decision-making problems is the Interactive Partially Observable Markov Decision Processes (I-POMDPs), which explicitly models the other agents' beliefs up to a finite reasoning level in order to more accurately predict their actions. This paper proposes a new online approximate solver for I-POMDPs, called Interactive Nested Tree Monte-Carlo Planning (I-NTMCP), that combines Monte Carlo Tree Search with the finite nested-reasoning construction of I-POMDPs. Unlike existing full-width I-POMDP planners, I-NTMCP focuses planning on the set of beliefs at each nesting level which are reachable under an optimal policy and uses sampling to construct and update policies at each nesting level, online. This strategy enables I-NTMCP to plan effectively in significantly larger I-POMDP problems and to deeper reasoning levels than has previously been possible. We demonstrate I-NTMCP's effectiveness on two competitive environments. The results indicate that I-NTMCP can generate substantially better policies up to more than 50× faster than I-POMDP Lite - one of the fastest I-POMDP solvers today. In the pursuit-evasion domain, we show I-NTMCP can plan effectively in a complex problem with over 88K states, which is two orders of magnitude larger than existing I-POMDP planning benchmark problems.

Planning under partial obervability is essential for autonomous robots. A principled way to address such planning problems is the Partially Observable Markov Decision Process (POMDP). Although solving POMDPs is computationally intractable, substantial advancements have been achieved in developing approximate POMDP solvers in the past two decades. However, computing robust solutions for problems with continuous observation spaces remains challenging. Most on-line solvers rely on discretising the observation space or artificially limiting the number of observations that are considered during planning to compute tractable policies. In this paper we propose a new on-line POMDP solver, called Lazy Belief Extraction for Continuous Observation POMDPs (LABECOP), that combines methods from Monte-Carlo-Tree-Search and particle filtering to construct a policy reprentation which doesn't require discretised observation spaces and avoids limiting the number of observations considered during planning. Experiments on three different problems involving continuous observation spaces indicate that LABECOP performs similar or better than state- of-the-art POMDP solvers.

Service robots require the ability to recognize various household objects in order to carry out certain tasks, such as fetching an object for a person. Manually collecting information on all the objects a robot may encounter in a household is tedious and time-consuming; therefore this paper proposes the use of large-scale data from existing trademark databases. These databases contain logo images and a description of the goods and services the logo was registered under. For example, Pepsi is registered under soft drinks. We extend domain randomization in order to generate synthetic data to train a convolutional neural network logo detector, which outperformed previous logo detectors trained on synthetic data. We also provide a practical implementation for object fetching on a robot, which uses a Kinect and the logo detector to identify the object the human user requested. Tests on this robot indicate promising results, despite not using any real world photos for training.

Planning under partial observability is both challenging and critical for reliable robot operation. The past decade has seen substantial advances in this domain: The mathematically principled approach for addressing such problems, namely the Partially Observable Markov Decision Process (POMDP), has started to become practical for various robotics tasks. Good approximate solutions for problems framed as POMDPs can now be computed on-line, with a few classes of problems being solved in near real-time. However, applications of these more recent advances are often hindered by the lack of easy-to-use software tools. Implementation of state of the art algorithms exist, but most (if not all)require the POMDP model to be hard-coded inside the program, increasing the difficulty of applying them. To alleviate this problem, we propose a software toolkit, called On-line POMDP Planning Toolkit (OPPT)(downloadable from http://robotics.itee.uq.edu.au/~oppt). By providing a well-defined and general abstract solver API, OPPT enables the user to quickly implement new POMDP solvers. Furthermore, OPPT provides an easy-to-use plug-in architecture with interfaces to the high-fidelity simulator Gazebo that, in conjunction with user-friendly configuration files, allows users to specify POMDP models of a standard class of robot motion planning under partial observability problems with no additional coding effort.

For agile, accurate autonomous robotics, it is desirable to plan motion in the presence of uncertainty. The Partially Observable Markov Decision Process (POMDP) provides a principled framework for this. Despite the tremendous advances of POMDP-based planning, most can only solve problems with a small and discrete set of actions. This paper presents General Pattern Search in Adaptive Belief Tree (GPS-ABT), an approximate and online POMDP solver for problems with continuous action spaces. Generalized Pattern Search (GPS) is used as a search strategy for action selection. Under certain conditions, GPS-ABT converges to the optimal solution in probability. Results on a box pushing and an extended Tag benchmark problem are promising.

This paper introduces autonomous sorting of moving coins via a robot as a multi-level task that supports the principled study of robotics fundamentals including kinematics, dynamics, perception, motion planning, controls, and optimization based around a widely obtainable, standardized, low-cost object (a coin). The paper also presents a demonstrated solution to this in the form of the CHARM (Coin Handling Arm for Robotics Mastery) robot, which addresses the autonomous coin sorting problem using an economical kit made from commodity computing hardware and three Dynamixel servomotors. From a learning perspective, this problem facilitates interdisciplinary practice across subject and grade levels with an algorithmic foundation that is central to modern robotics. Evidence supporting this approach is illustrated from case studies of student projects and, in particular, the CHARM robot. Beyond practice alone, by presenting a challenging (but manageable) research problem, we found that the coin sorting task teaches robotics in a principled way. Further, algorithmic complexity tiers the problem to academic levels. While motivated by robotics education, the (optimal) coin sorting problem may also be seen as an archetype problem for manipulation/motion-planning research. Thus, this also promotes a research foundation supporting later research opportunities.

This paper proposes a new inspection planning algorithm, called Random Inspection Tree Algorithm (RITA). Given a perfect model of a structure, sensor specifications, robot's dynamics, and an initial configuration of a robot, RITA computes the optimal inspection trajectory that observes all points on the structure. Many inspection planning algorithms have been proposed, most of them consist of two sequential steps. In the first step, they compute a small set of observation points such that each point on the structure is visible. In the second step, they compute the shortest trajectory to visit all observation points at least once. The robot's kinematic and dynamic constraints are taken into account only in the second step. Thus, when the robot has differential constraints and operates in cluttered environments, the observation points may be difficult or even infeasible to reach. To alleviate this difficulty, RITA computes both observation points and the trajectory to visit the observation points simultaneously. RITA uses sampling-based techniques to find admissible trajectories with decreasing cost. Simulation results for 2-D environments are promising. Furthermore, we present analysis on the probabilistic completeness and asymptotic optimality of our algorithm.

Over the last eight years, significant scientific effort has been dedicated on the problem of 3-D surface reconstruction for structural systems. However, the critical area of marine structures remains insufficiently studied. The research presented here focuses on the problem of 3-D surface reconstruction in the marine environment. This work is an extension of our previous approach, in which a surface vehicle that was equipped with a powerful laser scanner was designed and used to scan the above-water part of the marine structure of interest. Here we propose the design of a novel surface vehicle that is capable of using laser scanners and a side-looking sonar to scan marine structures both above and below the waterline. We also study the issue of downsampling the dataset in order to perform efficient surface reconstruction of the considered 3-D geometry, and we present a methodology for combining and integrating data from the above- and below-water parts of the structure. To illustrate the proposed robotic platform and validate our algorithms, we present results from a set of experiments in the Singapore Sea. Specifically, we present 2 different maps: the above-water map and the combined above-and below-water map. In both cases, we have two different maps: a lower quality map, that can be generated on-line, and a higher quality map that is generated off-line. To the best of our knowledge, our work is the only one that provides a 3-D model for both above- and below-water parts of marine structures. In this work we assumed a GPS-denied environment, without using any other navigation sensor such as DVL or INS.

Path deformation is a technique that was introduced to generate robot motion wherein a path, that has been computed beforehand, is continuously deformed on-line in response to unforeseen obstacles. This paper introduces the first trajectory deformation scheme as an effort to improve path deformation. The main idea is that by incorporating the time dimension and hence information on the obstacles' future behaviour, quite a number of situations where path deformation would fail can be handled. The trajectory deformation scheme presented operates in two steps, ie, a collision avoidance step and a connectivity maintenance step, hence its name 2-step-trajectory-deformer (2-STD). In the collision avoidance step, repulsive forces generated by the obstacles deform the trajectory so that it remains collision-free. The purpose of the connectivity maintenance step is to ensure that the deformed trajectory remains feasible, ie, that it satisfies the robot's kinematic and/or dynamic constraints. Moreover, unlike path deformation wherein spatial deformation only takes place, 2-STD features both spatial and temporal deformation. It has been tested successfully on a planar robot with double integrator dynamics moving in dynamic environments.

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but they behave poorly when a robot's configuration space contains narrow passages. This paper presents workspace importance sampling (WIS), a new sampling strategy for PRM planning. Our main idea is to use geometric information from a robot's workspace as "importance" values to guide sampling in the corresponding configuration space. By doing so, WIS increases the sampling density in narrow passages and decreases the sampling density in wide-open regions. We tested the new planner on rigid-body and articulated robots in 2-D and 3-D environments. Experimental results show that WIS improves the planner's performance for path planning problems with narrow passages.