Improving the performance of motion planning algorithms for high-degree-of-freedom robots usually requires reducing the cost or frequency of computationally expensive operations. Traditionally, and especially for asymptotically optimal sampling-based motion planners, the most expensive operations are local motion validation and querying the nearest neighbours of a configuration. Recent advances have significantly reduced the cost of motion validation by using single instruction/multiple data (SIMD) parallelism to improve solution times for satisficing motion planning problems. These advances have not yet been applied to asymptotically optimal motion planning. This paper presents Fully Connected Informed Trees (FCIT*), the first fully connected, informed, anytime almost-surely asymptotically optimal (ASAO) algorithm. FCIT* exploits the radically reduced cost of edge evaluation via SIMD parallelism to build and search fully connected graphs. This removes the need for nearest-neighbours structures, which are a dominant cost for many sampling-based motion planners, and allows it to find initial solutions faster than state-of-the-art ASAO (VAMP, OMPL) and satisficing (OMPL) algorithms on the MotionBenchMaker dataset while converging towards optimal plans in an anytime manner.

Long-horizon task planning is important for robot autonomy, especially as a subroutine for frameworks such as Integrated Task and Motion Planning. However, task planning is computationally challenging and struggles to scale to realistic problem settings. We propose to accelerate task planning over an agent’s lifetime by integrating abstract strategies: a generalizable planning experience encoding introduced in earlier work. In this work, we contribute a practical approach to planning with strategies by introducing a novel formalism of planning in a strategy-augmented domain. We also introduce and formulate the notion of a strategy’s affordance, which indicates its predicted benefit to the solution, and use it to guide the planning and strategy grounding processes. Together, our observations yield an affordance-directed, lazy-search planning algorithm, which can seamlessly compose strategies and actions to solve long-horizon planning problems. We evaluate our planner in an object rearrangement domain, where we demonstrate performance benefits relative to a state-of-the-art task planner.

Motion planning under sensing uncertainty is critical for robots in unstructured environments, to guarantee safety for both the robot and any nearby humans. Most work on planning under uncertainty does not scale to high-dimensional robots such as manipulators, assumes simplified geometry of the robot or environment, or requires per-object knowledge of noise. Instead, we propose a method that directly models sensor-specific aleatoric uncertainty to find safe motions for high-dimensional systems in complex environments, without exact knowledge of environment geometry. We combine a novel implicit neural model of stochastic signed distance functions with a hierarchical optimization-based motion planner to plan low- risk motions without sacrificing path quality. Our method also explicitly bounds the risk of the path, offering trustworthiness. We empirically validate that our method produces safe motions and accurate risk bounds and is safer than baseline approaches.

Modern sampling-based motion planning algorithms typically take between hundreds of milliseconds to dozens of seconds to find collision-free motions for high degree-of-freedom problems. This paper presents performance improvements of more than 500x over the state-of-the-art, bringing planning times into the range of microseconds and solution rates into the range of kilohertz, without specialized hardware. Our key insight is how to exploit fine-grained parallelism within planning, providing generality-preserving algorithmic improvements to any such planner and significantly accelerating critical subroutines, such as forward kinematics and collision checking. We demonstrate our approach over a diverse set of challenging, realistic problems for complex robots ranging from 7 to 14 degrees-of-freedom. Moreover, we show our approach does not require high-power hardware by evaluating on a low-power single-board computer. The planning speeds demonstrated are fast enough to reside in the range of control frequencies and open up new avenues of motion planning research.

3D object reconfiguration encompasses common robot manipulation tasks in which a set of objects must be moved through a series of physically feasible state changes into a desired final configuration. Object reconfiguration is challenging to solve in general, as it requires efficient reasoning about environment physics that determine action validity. This information is typically manually encoded in an explicit transition system. Constructing these explicit encodings is tedious and error-prone, and is often a bottleneck for planner use. In this work, we explore embedding a physics simulator within a motion planner to implicitly discover and specify the valid actions from any state, removing the need for manual specification of action semantics. Our experiments demonstrate that the resulting simulation-based planner can effectively produce physically valid rearrangement trajectories for a range of 3D object reconfiguration problems without requiring more than an environment description and start and goal arrangements.

Integrated task and motion planning (TMP) offers a promising class of approaches for solving robot planning problems with intricate symbolic and geometric constraints. However, TMP planners rely on difficult-to-construct abstract models of robot actions. In this article, we propose a method for automatically constructing and continuously improving an abstraction of robot actions via observations of the robot performing the actions. This method, calledautomatic abstraction repair, allows action abstractions to be initially incorrect or incomplete and converge toward a correct model over time. Here, we demonstrate abstraction repair using constrained polynomial zonotopes (CPZs), an expressive nonconvex set representation for modeling predicates over joint symbolic and geometric state. The repair process performs a hybrid optimizing search over symbolic edit operations to predicate formulae and continuous predicate parameters to improve the grounding of the abstraction to the behavior of a physical robot. In this work, we describe the predicate model, introduce thesymbolic-geometric abstraction repairproblem, and present an anytime algorithm for automatic abstraction repair. We demonstrate that abstraction repair can improve realistic action abstractions for common mobile manipulation actions from a handful of observations and discuss the tradeoffs of the CPZ model for predicate representation.

Mobile robots struggle to integrate seamlessly in crowded environments such as pedestrian scenes, often disrupting human activity. One obstacle preventing their smooth integration is our limited understanding of how humans may perceive and react to robot motion. Motivated by recent studies highlighting the benefits of intent-expressive motion for robots operating close to humans, we describe Social Momentum (SM), a planning framework for legible robot motion generation in multiagent domains. We investigate the properties of motion generated by SM via two large-scale user studies: an online, video-based study ( N = 180) focusing on the legibility of motion produced by SM and a lab study ( N = 105) focusing on the perceptions of users navigating next to a robot running SM in a crowded space. Through statistical and thematic analyses of collected data, we present evidence suggesting that (a) motion generated by SM enables quick inference of the robot’s navigation strategy; (b) humans navigating close to a robot running SM follow comfortable, low-acceleration paths; and (c) robot motion generated by SM is positively perceived and indistinguishable from a teleoperated baseline. Through the discussion of experimental insights and lessons learned, this article aspires to inform future algorithmic and experimental design for social robot navigation.

Intent-expressive robot motion has been shown to result in increased efficiency and reduced planning efforts for copresent humans. Existing frameworks for generating intent-expressive robot behaviors have typically focused on applications in static or structured environments. Under such settings, emphasis is placed towards communicating the robot»s intended final configuration to other agents. However, in dynamic, unstructured and multi-agent domains, such as pedestrian environments, knowledge of the robot»s final configuration is not sufficiently informative as it completely ignores the complex dynamics of interaction among agents. To address this problem, we design a planning framework that aims at generating motion that clearly communicates an agent»s intended collision avoidance strategy rather than its destination. Our framework estimates the most likely intended avoidance protocols of others based on their past behaviors, superimposes them, and generates an expressive and socially compliant robot action that reinforces the expectations of others regarding these avoidance protocols. This action facilitates inference and decision making for everyone, as illustrated in the simplified topological pattern of agents» trajectories. Extensive simulations demonstrate that our framework consistently achieves significantly lower topological complexity, compared against common benchmark approaches in multi-agent collision avoidance. The significance of this result for real world applications is demonstrated by a user study that reveals statistical evidence suggesting that multi-agent trajectories of lower topological complexity tend to facilitate inference for observers.