This paper proposes a novel planning framework to handle a multi-agent pathfinding problem under a team-connected communication constraint, where all agents must have a connected communication channel to the rest of the team during their entire movements. Standard multi-agent pathfinding approaches (e.g., priority-based search) have potential in this domain but routinely fail when neighboring configurations at start and goal differ. Their single-expansion approach—computing each agent’s path from the start to the goal in just a single expansion—cannot reliably handle planning under communication constraints for agents as their neighbors change during navigating. Similarly, leader-follower approaches (e.g., platooning) are effective at maintaining team communication, but fixing the leader at the outset of planning can cause planning to become stuck in dense-clutter environments, limiting their practical utility. To overcome this limitation, we propose a novel two-level multi-agent pathfinding framework that integrates two techniques: adaptive path expansion to expand agent paths to their goals in multiple stages; and dynamic leading technique that enables the reselection of the leading agent during each agent path expansion whenever progress cannot be made. Simulation experiments show the efficiency of our planning approach, which can handle up to 25 agents across five environment types under a limited communication range constraint and up to 11–12 agents on three environments types under line-of-sight communication constraint, exceeding 90 % success-rate where baselines routinely fail.

Despite their promise to perform complex reasoning, large language models (LLMs) have been shown to have limited effectiveness in end-to-end planning. This has inspired an intriguing question: if these models cannot plan well, can they still contribute to the planning framework as a helpful plan evaluator? In this work, we generalize this question to consider LLMs augmented with visual understanding, i.e., Vision-Language Models (VLMs). We introduce PathEval, a novel benchmark evaluating VLMs as plan evaluators in complex path-planning scenarios. Succeeding in the benchmark requires a VLM to be able to abstract traits of optimal paths from the scenario description, demonstrate precise low-level perception on each path, and integrate this information to decide the better path. Our analysis of state-of-the-art VLMs reveals that these models face significant challenges on the benchmark. We observe that the VLMs can precisely abstract given scenarios to identify the desired traits and exhibit mixed performance in integrating the provided information. Yet, their vision component presents a critical bottleneck, with models struggling to perceive low-level details about a path. Our experimental results show that this issue cannot be trivially addressed via end-to-end fine-tuning; rather, task-specific discriminative adaptation of these vision encoders is needed for these VLMs to become effective path evaluators.12

Autonomous mobile robots (e.g., warehouse logistics robots) often need to traverse complex, obstacle-rich, and changing environments to reach multiple fixed goals (e.g., ware-house shelves). Traditional motion planners need to calculate the entire multi-goal path from scratch in response to changes in the environment, which results in a large consumption of computing resources. This process is not only time-consuming but also may not meet real-time requirements in application scenarios that require rapid response to environmental changes. In this paper, we provide a novel Multi-Goal Motion Memory technique11https://github.com/yuanjielu-64/MGMM_ICRA2025.git that allows sampling-based motion planners to use previous planning experiences to accelerate future multi-goal planning in changing environments. This algorithm allows robots to use previous planning experiences to accelerate future multi-goal planning in changing environments. Specifically, our approach predicts dynamically feasible trajectories and distances between goal pairs to guide the sampling process to construct a motion map, to inform Traveling Salesman Problem (TSP) solvers to compute a tour, and to efficiently produce motion plans. Experiments conducted with a vehicle and a snake-like robot in obstacle-rich environments show that the proposed Motion Memory technique can substantially accelerate planning speed by up to 90%. Furthermore, the solution quality is comparable to state-of-the-art algorithms and even better in some environments.

When facing a new motion-planning problem, most motion planners solve it from scratch, e.g., via sampling and exploration or starting optimization from a straight-line path. However, most motion planners have to experience a variety of planning problems throughout their lifetimes, which are yet to be leveraged for future planning. In this paper, we present a simple but efficient method called Motion Memory, which allows different motion planners to accelerate future planning using past experiences. Treating existing motion planners as either a closed or open box, we present a variety of ways that Motion Memory can contribute to reduce the planning time when facing a new planning problem. We provide extensive experiment results with three different motion planners on three classes of planning problems with over 30,000 problem instances and show that planning speed can be significantly reduced by up to 89% with the proposed Motion Memory technique and with increasing past planning experiences.

We present a novel approach to learning-augmented, long-horizon navigation under uncertainty in large-scale environments in which considering the robot dynamics is essential for informing good behavior. Our approach tightly integrates sampling-based motion planning, which computes dynamically feasible routes to the goal through different unexplored boundaries, and a high-level planner that leverages predictions about unseen space to select a route that best makes progress toward the unseen goal. Owing to its ability to understand the impacts of the robot’s dynamics on how it should attempt to reach the goal, our approach achieves both higher reliability and improved navigation performance compared to competitive learning-informed and non-learned baselines in simulated office-building-like environments.

Multi-goal motion planning requires a robot to plan collision-free and dynamically-feasible motions to reach multiple goals, often in unstructured, obstacle-rich environments. This is challenging due to the complex dependencies between navigation and high-level reasoning, requiring the robot to explore a vast space of feasible motions and goal sequences. Our approach combines machine learning and Traveling Salesman Problem (TSP) solvers with sampling-based motion planning. Machine learning predicts distances and directions between locations, considering obstacles and robot dynamics, which the TSP solver uses to compute promising tours. Sampling-based motion planning expands a motion tree to follow the tours along the predicted directions. We demonstrate the effectiveness of our approach through experiments with vehicle and snake-like robot models operating in unstructured environments with multiple goals.

As the future of autonomous underwater vehicle (AUV) deployments tends to multi-vehicle systems, new approaches in coordination and control are needed. In this work, we consider the problem of simultaneous survey and inspection where one vehicle dynamically discovers objects while another vehicle must inspect as many of the objects as possible over the course of the mission. This requires a fully autonomous inspection vehicle, and to this end, we present a planning approach which couples sampling-based motion planning with timed roadmap constraints as well as a real-time execution framework. The methods presented address the underlying challenges that arise during simultaneous survey and inspection using AUVs, namely those of communication constraints, safety of navigation constraints, and dynamically discovered tasks. Additionally, we present field results for the simultaneous survey and inspection mission using teamed AUVs.

In marine robotics, data-collection operations often require an autonomous underwater vehicle (AUV) to collaborate with an unmanned surface vehicle (USV). The mission for the AUV is to reach many goal locations, avoid obstacles and unsafe areas, and maintain communication with the USV. The goals, however, are not known a priori, but are dynamically discovered by the USV as it moves along a predefined path. The USV communicates the discovered goals to the AUV along with rewards for reaching each goal to incentivize the AUV to increase the sum of the rewards when obstacles, time, and communication constraints make it impossible to reach all the goals. We develop a framework comprised of an execution module and a multi-layered planner to enable the AUV to avoid collisions, maintain communication with the USV, and increase the sum of the rewards by reaching many of the discovered goals. The execution module enables the AUV to follow the planned motions, invoking the planner when new goals are discovered. To facilitate navigation, the planner constructs a 3D roadmap that captures the connectivity of the environment by sampling and connecting waypoints in the free space. The high-level planning layer is based on informed discrete search to find roadmap paths that satisfy the communication constraints and increase the sum of the goal rewards. The low-level layer uses sampling-based motion planning to expand a tree of feasible motions along these roadmap paths. The layers interact to update the planned motions as new goals are discovered. Experiments using 3D environments and an increasing number of goals demonstrate the efficiency of the approach to solve dynamic multi-goal motion-planning problems with communication constraints.Note to Practitioners—This paper is motivated by the problem of at-sea data collection using unmanned vehicles where inter-vehicle communications constraints must be maintained. This is a challenging problem that has generally required significant human monitoring and intervention due to the communication constraints and planning challenges. In this paper, we leverage recent advances in underwater communications and focus on new problems that arise in the planning space, specifically, how we generate trajectories for an AUV that satisfies communication range constraints while still performing an underlying task. We show that it is possible to plan for an AUV in real-time while considering these constraints. This paper suggests that our approach can support these complex at-sea missions. Future research will focus on field deployments and introducing more uncertainty into the underlying sensor models during planning.

While sampling-based approaches have made significant progress, motion planning with dynamics still poses significant challenges as the planner has to generate not only collision-free but also dynamically-feasible trajectories that enable the robot to reach its goal. To improve the efficiency of sampling-based motion planners, this paper develops a framework, termed Motion-Planning Runtime Prediction (MPRP), that relies on machine learning to train models to predict the expected runtime of a planner. When solving a new motion-planning problem, the trained model is then incorporated into the motion planner to more effectively guide the search toward parts of the state space that are associated with low expected runtime predictions. This paper applies the MPRP framework to state-of-the-art sampling-based motion planners to obtain new planners, which are shown to be significantly faster.

This paper studies the multi-robot motion-planning problem with unlabeled goals where n robots have to reach m goals. The proposed approach also takes into account the underlying dynamics of each robot to produce dynamically-feasible trajectories that enable the robots to reach all the goals while avoiding collisions with the obstacles and each other. The approach leverages the idea of combining sampling-based motion planning with goal assignment and multi-agent search. In fact, the goal-assignment layer seeks to effectively utilize the robots based on estimated costs to reach the remaining goals. The multi-agent search provides nonconflicting paths over roadmap graphs, which then guide the sampling-based expansion of a motion tree. The goal assignments and multi-agent paths are frequently updated based on the progress made during the motion-tree expansion. Simulation experiments using an increasing number of robots with nonlinear dynamics demonstrate the efficiency of the approach.

Humans assume different production roles in a workspace. On one hand, humans design workplans to complete tasks as efficiently as possible in order to improve productivity. On the other hand, a nice workspace is essential to facilitate teamwork. In this way, workspace design and workplan design complement each other. Inspired by such observations, we propose an automatic approach to jointly design a workspace and a workplan. Taking staff properties, a space, and work equipment as input, our approach jointly optimizes a workspace and a workplan, considering performance factors such as time efficiency and congestion avoidance, as well as workload factors such as walk effort, turn effort, and workload balances. To enable exploration of design trade-offs, our approach generates a set of Pareto-optimal design solutions with strengths on different objectives, which can be adopted for different work scenarios. We apply our approach to synthesize workspaces and workplans for different workplaces such as a fast food kitchen and a supermarket. We also extend our approach to incorporate other common work considerations such as dynamic work demands and accommodating staff members with different physical capabilities. Evaluation experiments with simulations validate the efficacy of our approach for synthesizing effective workspaces and workplans.

BACKGROUND: Nearly all cellular processes involve proteins structurally rearranging to accommodate molecular partners. The energy landscape underscores the inherent nature of proteins as dynamic molecules interconverting between structures with varying energies. In principle, reconstructing a protein's energy landscape holds the key to characterizing the structural dynamics and its regulation of protein function. In practice, the disparate spatio-temporal scales spanned by the slow dynamics challenge both wet and dry laboratories. However, the growing number of deposited structures for proteins central to human biology presents an opportunity to infer the relevant dynamics via exploitation of the information encoded in such structures about equilibrium dynamics. RESULTS: Recent computational efforts using extrinsic modes of motion as variables have successfully reconstructed detailed energy landscapes of several medium-size proteins. Here we investigate the extent to which one can reconstruct the energy landscape of a protein in the absence of sufficient, wet-laboratory structural data. We do so by integrating intrinsic modes of motion extracted off a single structure in a stochastic optimization framework that supports the plug-and-play of different variable selection strategies. We demonstrate that, while knowledge of more wet-laboratory structures yields better-reconstructed landscapes, precious information can be obtained even when only one structural model is available. CONCLUSIONS: The presented work shows that it is possible to reconstruct the energy landscape of a protein with reasonable detail and accuracy even when the structural information about the protein is limited to one structure. By attenuating the dependence on structural data of methods designed to compute protein energy landscapes, the work opens up interesting venues of research on structure-based inference of dynamics. Of particular interest are directions of research that will extend such inference to proteins with no experimentally-characterized structures.

This paper presents an effective multi-robot motion planner that enables each robot to reach its desired location while avoiding collisions with the other robots and the obstacles. The approach takes into account the differential constraints imposed by the underlying dynamics of each robot and generates dynamically-feasible motions that can be executed in the physical world. The crux of the approach is the sampling-based expansion of a motion tree in the continuous state space of all the robots guided by multi-agent search over a discrete abstraction. Experiments using vehicle models with nonlinear dynamics operating in complex environments show significant speedups over related work.

This paper presents an effective, cooperative, and probabilistically-complete multi-robot motion planner that enables each robot to move to a desired location while avoiding collisions with obstacles and other robots. The approach takes into account not only the geometric constraints arising from collision avoidance, but also the differential constraints imposed by the motion dynamics of each robot. This makes it possible to generate collision-free and dynamically-feasible trajectories that can be executed in the physical world.The salient aspect of the approach is the coupling of sampling-based motion planning to handle the complexity arising from the obstacles and robot dynamics with multi-agent search to find solutions over a suitable discrete abstraction. The discrete abstraction is obtained by constructing roadmaps to solve a relaxed problem that accounts for the obstacles but not the dynamics. Sampling-based motion planning expands a motion tree in the composite state space of all the robots by adding collision-free and dynamically-feasible trajectories as branches. Efficiency is obtained by using multi-agent search to find non-conflicting routes over the discrete abstraction which serve as heuristics to guide the motion-tree expansion. When little or no progress is made, the routes are penalized and the multi-agent search is invoked again to find alternative routes. This synergistic coupling makes it possible to effectively plan collision-free and dynamically-feasible motions that enable each robot to reach its goal. Experiments using vehicle models with nonlinear dynamics operating in complex environments, where cooperation among robots is required, show significant speedups over related work.

Abstract Toward enhancing automation, this paper proposes an efficient approach for multi‐group motion planning, where the set of goals is divided intokgroups and the objective is to compute a collision‐free and dynamically feasible trajectory that enables a virtual vehicle to reach at least one goal from each group. The approach works with ground and aerial vehicles operating in complex environments containing numerous obstacles. In addition to modeling the vehicle dynamics by differential equations, the approach can use physics‐based game engines, which provide an increased level of realism. The approach is based on a hybrid search that uses generalized traveling salesman tours over a probabilistic roadmap to effectively guide the sampling‐based expansion of a motion tree. As the motion tree is expanded with collision‐free and dynamically feasible trajectories, tours are adjusted based on a partition of the motion tree into equivalence classes. This gives the approach the flexibility to discover new tours that avoid collisions and are compatible with the vehicle dynamics. Comparisons to related work show significant improvements both in terms of runtime and solution length. Copyright © 2016 John Wiley & Sons, Ltd.

Proteins are macromolecules in perpetual motion, switching between structural states to modulate their function. A detailed characterization of the precise yet complex relationship between protein structure, dynamics, and function requires elucidating transitions between functionally-relevant states. Doing so challenges both wet and dry laboratories, as protein dynamics involves disparate temporal scales. In this paper, we present a novel, sampling-based algorithm to compute transition paths. The algorithm exploits two main ideas. First, it leverages known structures to initialize its search and define a reduced conformation space for rapid sampling. This is key to address the insufficient sampling issue suffered by sampling-based algorithms. Second, the algorithm embeds samples in a nearest-neighbor graph where transition paths can be efficiently computed via queries. The algorithm adapts the probabilistic roadmap framework that is popular in robot motion planning. In addition to efficiently computing lowest-cost paths between any given structures, the algorithm allows investigating hypotheses regarding the order of experimentally-known structures in a transition event. This novel contribution is likely to open up new venues of research. Detailed analysis is presented on multiple-basin proteins of relevance to human disease. Multiscaling and the AMBER ff14SB force field are used to obtain energetically-credible paths at atomistic detail.

Many pathogenic mutations percolate to protein dysfunction by altering dynamics. Reconstructing protein energy landscapes promises to relate dynamics to function but is generally infeasible due to the disparate spatio-temporal scales involved. Recent algorithmic innovation allows reconstructing energy landscapes of medium-size proteins in the presence of sufficient prior wet-laboratory structure data. The ability to do so on healthy and pathogenic variants of a protein is renewing the need for landscape analysis and comparison. Here we describe a novel landscape analysis method that detects altered landscape features in response to mutations and allows formulating hypotheses on the impact of mutations on (dys)function. This work opens up interesting avenues into automated analysis and summarization of landscapes.

More than fifty years of research in molecular biology have demonstrated that the ability of small and large molecules to interact with one another and propagate the cellular processes in the living cell lies in the ability of these molecules to assume and switch between specific structures under physiological conditions. Elucidating biomolecular structure and dynamics at equilibrium is therefore fundamental to furthering our understanding of biological function, molecular mechanisms in the cell, our own biology, disease, and disease treatments. By now, there is a wealth of methods designed to elucidate biomolecular structure and dynamics contributed from diverse scientific communities. In this survey, we focus on recent methods contributed from the Robotics community that promise to address outstanding challenges regarding the disparate length and time scales that characterize dynamic molecular processes in the cell. In particular, we survey robotics-inspired methods designed to obtain efficient representations of structure spaces of molecules in isolation or in assemblies for the purpose of characterizing equilibrium structure and dynamics. While an exhaustive review is an impossible endeavor, this survey balances the description of important algorithmic contributions with a critical discussion of outstanding computational challenges. The objective is to spur further research to address outstanding challenges in modeling equilibrium biomolecular structure and dynamics.

This paper proposes an interactive search approach, termed INTERACT, which couples sampling-based motion planning with action planning in order to effectively solve the combined task and motion planning problem. INTERACT is geared towards scenarios involving a mobile robot operating in a fully known environment consisting of static and movable objects. INTERACT makes it possible to specify a task in the planning domain definition language (PDDL) and automatically computes a collision-free and dynamically feasible trajectory that enables the robot to accomplish the task. The coupling of sampling-based motion planning with action planning is made possible by expanding a tree of feasible motions and partitioning it into equivalence classes based on the task predicates. Action plans provide guidance as to which a equivalence class should be further expanded. Information gathered during the motion tree expansion is used to adjust the action costs in order to effectively guide the expansion towards the goal. This interactive process of selecting an equivalence class, expanding the motion tree to implement its action plan and updating the action costs and plans to reflect the progress made is repeated until a solution is found. Experimental validation is provided in simulation using a robotic vehicle to accomplish sophisticated pick-and-place tasks. Comparisons to previous work show significant improvements.

Proteins are macromolecules in perpetual motion, switching between structural states to modulate their function. A detailed characterization of the precise yet complex relationship between protein structure, dynamics, and function requires elucidating transitions between functionally-relevant states. Doing so challenges both wet and dry laboratories, as protein dynamics involves disparate temporal scales. In this paper we present a novel, sampling-based algorithm to compute transition paths. The algorithm exploits two main ideas. First, it leverages known structures to initialize its search and define a reduced conformation space for rapid sampling. This is key to address the insufficient sampling issue suffered by sampling-based algorithms. Second, the algorithm embeds samples in a nearest-neighbor graph where transition paths can be efficiently computed via queries. The algorithm adapts the probabilistic roadmap framework that is popular in robot motion planning. In addition to efficiently computing lowest-cost paths between any given structures, the algorithm allows investigating hypotheses regarding the order of experimentally-known structures in a transition event. This novel contribution is likely to open up new venues of research. Detailed analysis is presented on multiple-basin proteins of relevance to human disease. Multiscaling and the AMBER ff12SB force field are used to obtain energetically-credible paths at atomistic detail.

This paper proposes a reactive motion-planning approach for persistent surveillance of risk-sensitive areas by a team of unmanned aerial vehicles (UAVs). The planner, termed PARCov (Planner for Autonomous Risk-sensitive Coverage), seeks to: i) maximize the area covered by sensors mounted on each UAV; ii) provide persistent surveillance; iii) maintain high sensor data quality; and iv) reduce detection risk. To achieve the stated objectives, PARCov combines into a cost function the detection risk with an uncertainty measure designed to keep track of the regions that have been surveyed and the times they were last surveyed. PARCov reduces the uncertainty and detection risk by moving each quadcopter toward a low-cost region in its vicinity. By reducing the uncertainty, PARCov is able to increase the coverage and provide persistent surveillance. Moreover, a nonlinear optimization formulation is used to determine the optimal altitude for flying each quadcopter in order to maximize the sensor data quality while minimizing risk.

This paper presents a motion planner, termed Guided Sampling Tree (GUST), geared toward mobile robots with nonlinear dynamics and nonholonomic constraints operating in complex environments. GUST expands a tree of collision-free and dynamically feasible motions and uses a workspace decomposition to partition the motion tree into groups. GUST relies on shortest path distances in the workspace decomposition and penalty factors to identify candidate groups, which could result in rapid expansions of the motion tree toward the goal. The initial workspace decomposition and the partition of the motion tree are further refined during the search in order to improve the group selection and the motion-tree expansion. Experimental validation is provided using ground and aerial-vehicle models operating in complex environments. Comparisons with related work show statistically significant speedups with large effect sizes.

This paper focuses on motion-planning problems for high-dimensional mobile robots with nonlinear dynamics operating in complex environments. It is motivated by a recent framework that combines sampling-based motion planning in the state space with discrete search over a workspace decomposition. Building on this line of work, the premise of this paper is that the computational efficiency can be significantly improved by tightly coupling sampling-based motion planning with probabilistic roadmap abstractions instead of workspace decompositions. Probabilistic roadmap abstractions are constructed over a low-dimensional configuration space obtained by considering relaxed and simplified representations of the robot model and its feasible motions. By capturing the connectivity of the free configuration space, roadmap abstractions provide the framework with promising suggestions of how to effectively expand the sampling-based search in the full state space. Experiments with high-dimensional robot models, nonlinear dynamics, and nonholonomic constraints show significant computational speedups over related work.

This paper presents an efficient approach for planning collision-free, dynamically-feasible, and low-cost motion trajectories that satisfy task specifications given as formulas in a temporal logic, namely Syntactically Co-Safe Linear Temporal Logic (LTL). The planner is geared toward high-dimensional mobile robots with nonlinear dynamics operating in complex environments. The planner incorporates physics-based engines for accurate simulations of rigid-body dynamics. To obtain computational efficiency and generate low-cost solutions, the planner first imposes a discrete abstraction by combining an automaton representing the LTL formula with a workspace decomposition. The planner then uses the discrete abstraction to induce a partition of a sampling-based motion tree being expanded in the state space into equivalence classes. Each equivalence class captures the progress made toward achieving the temporal logic specifications. Heuristics defined over the abstraction are used to estimate the feasibility of expanding the motion tree from these equivalence classes and reaching an accepting automaton state. Costs are adjusted based on progress made, giving the planner the flexibility to make rapid progress while discovering new ways to expand the search. Comparisons to related work show statistically significant computational speedups and reduced solution costs.

This paper pursues multi-goal motion planning, where the overall set of goals is divided into k groups and the virtual agent needs to visit at least one goal per group. We have developed a combined task and motion-planning approach which can work with ground and aerial vehicles whose motions are simulated by differential equations or by physics-based game engines. The proposed approach is based on a hybrid search, where the expansion of a motion tree in the continuous state space is guided by heuristic costs and generalized traveling salesman tours computed over a discrete abstraction. The discrete abstraction is obtained via a probabilistic roadmap constructed over a low-dimensional configuration space resulting from a simplified problem setting. By capturing the connectivity of the free configuration space and connecting the goals, the roadmap provides generalized traveling salesman tours that effectively guide the motion-tree expansion. Experiments demonstrate that the approach not only improves previous methodologies in terms of runtime and solution length but also that it is scalable with respect to both the number of goals and groups.

This paper presents a path-planning approach to enable a swarm of robots move to a goal region while avoiding collisions with static and dynamic obstacles. To provide scalability and account for the complexity of the interactions in the swarm, the proposed approach combines probabilistic roadmaps with potential fields. The underlying idea is to provide the swarm with a series of intermediate goals which are obtained by constructing and searching a roadmap of likely collision-free guides. As the swarm moves from one intermediate goal to the next, it relies on potential fields to quickly react and avoid collisions with static and dynamic obstacles. Potential fields are also used to ensure that the swarm moves in cohesion. When the swarm deviates or is unable to reach the planned intermediate goals due to interference from the dynamic obstacles, the roadmap is searched again to provide alternative guides. Experiments conducted in simulation demonstrate the efficiency and scalability of the approach.

This paper proposes a path-planning approach to enable a team of unmanned aerial vehicles (UAVs) to efficiently conduct surveillance of sensitive areas. The proposed approach, termed PARCov (Planner for Autonomous Risk-sensitive Coverage), seeks to maximize the area covered by the sensors mounted on each UAV while maintaining high sensor data quality and minimizing detection risk. PARCov leverages from swarm intelligence the idea of using simple interactions among UAVs to promote an emergent behavior that achieves the desired objectives. PARCov uses a dynamic grid to keep track of the parts of the space that have been surveyed and the times that they were last surveyed. This information is then used to move the UAVs toward areas that have not been covered in a long time. Moreover, a nonlinear optimization formulation is used to determine the altitude at which each UAV flies. The efficiency and scalability of PARCov is demonstrated in simulation using complex environments and an increasing number of UAVs to conduct risk-sensitive surveillance.

This paper presents a framework for motion planning with dynamics as hybrid search over the continuous space of feasible motions and the discrete space of a low-dimensional workspace decomposition. Each step of the hybrid search consists of expanding a frontier of regions in the discrete space using cost heuristics as guide followed by sampling-based motion planning to expand a tree of feasible motions in the continuous space to reach the frontier. The approach is geared towards robots with many degrees-of-freedom (DOFs), nonlinear dynamics, and nonholonomic constraints, which make it difficult to follow discrete-search paths to the goal, and hence require a tight coupling of motion planning and discrete search. Comparisons to related work show significant computational speedups.

Linear Temporal Logic makes it possible to express tasks in terms of propositions, logical connectives, and temporal connectives. This paper shows how to incorporate a subclass of LTL, namely co-safe LTL, into Probabilistic RoadMap (PRM) path planners. PRMs provide an important class of approaches which have been shown to work well for high-dimensional configuration spaces. The proposed Temporal-PRM approach combines the roadmap with a finite automaton representing the co-safe LTL formula φ and conducts the search over the combined graph. As a result, roadmap connections are reused when needed to find paths that satisfy φ. Experimental validation is provided in simulation by using different scenes, co-safe LTL specifications, a snake-like robot model with numerous degrees-of-freedom, and different sampling strategies.

To compute a motion trajectory that avoids collisions, reaches a goalregion, and satisfies differential constraints imposed by robotdynamics, this paper proposes an approach that conducts a guidedsearch over the continuous space of motions and over a discrete spaceobtained by a workspace decomposition. A tree of feasible motions anda frontier of workspace regions are expanded simultaneously by firstdetermining the next region along which to expand the search and thenusing sampling-based motion planning to add trajectories to the treeto reach the selected region. When motion planning is not able toreach the selected region, its cost is increased sothat the approach has the flexibility to expand the search along newregions. Comparisons to related work show significant computationalspeedups.

This paper develops a sensor- and sampling-based motion planner to control a surgical robot in order to explore osteolytic lesions in orthopedic surgery. Because of the difficulty of using conventional surgical tools, such exploration is needed in minimally-invasive treatments of ¿particle diseases,¿ which commonly result from material wear in total hip replacements. Since a geometric model of the osteolytic cavity is not always available, the planner relies only on a robot model that can detect collisions. As such, the planner can work in conjunction with real systems. The planner effectively combines global and local exploration. The global layer determines which regions to explore, while local exploration uses information gain to move the robot tip to positions in the region that increase exploration. Simulation experiments are conducted using a snake-like cannula robot on surgically-relevant osteolytic cavities. As desired in minimally-invasive treatment of osteolysis, performance is measured as the volume explored by the robot tip. The proposed method achieves 83-92% performance rate when compared to methods that require 3D models of osteolytic cavities. Comparisons to sensor-based related work (i.e., no 3D models) show significant improvements in performance.

This paper explores the connection between sensor-based perception and exploration in the context of haptic object identification. The proposed approach combines 1) object recognition from tactile appearance with 2) purposeful haptic exploration of unknown objects to extract appearance information. The recognition component brings to bear computer-vision techniques by viewing tactile-sensor readings as images. We present a bag-of-features framework that uses several tactile-image descriptors, some that are adapted from the vision domain and others that are novel, to estimate a probability distribution over object identity as an unknown object is explored. Haptic exploration is treated as a search problem in a continuous space to take advantage of sampling-based motion planning to explore the unknown object and construct its tactile appearance. Simulation experiments of a robot arm equipped with a haptic sensor at the end-effector provide promising validation, thereby indicating high accuracy in identifying complex shapes from tactile information gathered during exploration. The proposed approach is also validated by using readings from actual tactile sensors to recognize real objects.

To compute collision-free and dynamically-feasibile trajectories that satisfy high-level specifications given in a planning-domain definition language, this paper proposes to combine sampling-based motion planning with symbolic action planning. The proposed approach, Sampling-based Motion and Symbolic Action Planner (SMAP), leverages from sampling-based motion planning the underlying idea of searching for a solution trajectory by selectively sampling and exploring the continuous space of collision-free and dynamically-feasible motions. Drawing from AI, SMAP uses symbolic action planning to identify actions and regions of the continuous space that sampling-based motion planning can further explore to significantly advance the search. The planning layers interact with each-other through estimates on the utility of each action, which are computed based on information gathered during the search. Simulation experiments with dynamical models of vehicles carrying out tasks given by high-level STRIPS specifications provide promising initial validation, showing that SMAP efficiently solves challenging problems.

To efficiently solve challenges related to motion-planning problems with dynamics, this paper proposes treating motion planning not just as a search problem in a continuous space but as a search problem in a hybrid space consisting of discrete and continuous components. A multilayered framework is presented which combines discrete search and sampling-based motion planning. This framework is called synergistic combination of layers of planning ( SyCLoP) hereafter. Discrete search uses a workspace decomposition to compute leads, i.e., sequences of regions in the neighborhood that guide sampling-based motion planning during the state-space exploration. In return, information gathered by motion planning, such as progress made, is fed back to the discrete search. This combination allows SyCLoP to identify new directions to lead the exploration toward the goal, making it possible to efficiently find solutions, even when other planners get stuck. Simulation experiments with dynamical models of ground and flying vehicles demonstrate that the combination of discrete search and motion planning in SyCLoP offers significant advantages. In fact, speedups of up to two orders of magnitude were obtained for all the sampling-based motion planners used as the continuous layer of SyCLoP.

We have recently proposed DSLX, a motion planner that significantly reduces the computational time for solving challenging kinodynamic problems by interleaving continuous state-space exploration with discrete search on a workspace decomposition. An important but inadequately understood aspect of DSLX is the role of the workspace decomposition on the computational efficiency of the planner. Understanding this role is important for successful applications of DSLX to increasingly complex robotic systems. This work shows that the granularity of the workspace decomposition directly impacts computational efficiency: DSLX is faster when the decomposition is neither too fine-nor too coarse-grained. Finding the right level of granularity can require extensive fine-tuning. This work demonstrates that significant computational efficiency can instead be obtained with no fine-tuning by using conforming Delaunay triangulations, which in the context of DSLX provide a natural workspace decomposition that allows an efficient interplay between continuous state-space exploration and discrete search. The results of this work are based on extensive experiments on DSLX using grid, trapezoidal, and triangular decompositions of various granularities to solve challenging first and second-order kinodynamic motion-planning problems.

The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the online, open-source, programming system for motion planning (OOPSMP), a programming infrastructure that provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendible. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic Web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure

The rapidly increasing complexity of tasks robotic systems are expected to carry out underscores the need for the development of motion planners that can take into account discrete changes in the continuous motions of the system. Completion of tasks such as exploration of unknown or hazardous environments often requires discrete changes in the controls and motions of the robot in order to adapt to different terrains or maintain operability during partial failures or other mishaps. The contribution of this work toward this objective is the development of an efficient motion planner for a hybrid robotic system. The controls and motion equations of the robot could change discretely in order to enable the robot to operate in different terrains. The framework in this paper blends discrete searching with sampling-based motion planning for continuous state spaces and is well-suited for robotic systems modeled as hybrid systems with numerous discrete modes and transitions. This multi-layered approach offers considerable improvements over existing methods addressing similar problems, as indicated by the experimental results.

Nonlinear dimensionality reduction methods often rely on the nearest-neighbors graph to extract low-dimensional embeddings that reliably capture the underlying structure of high-dimensional data. Research however has shown that computing nearest neighbors of a point from a high-dimensional data set generally requires time proportional to the size of the data set itself, rendering the computation of the nearest-neighbors graph prohibitively expensive.

High-dimensional problems arising from complex robotic systems test the limits of current motion planners and require the development of efficient distributed motion planners that take full advantage of all the available resources. This paper shows how to effectively distribute the computation of the Sampling-based Roadmap of Trees (SRT) algorithm using a decentralized master-client scheme. The distributed SRT algorithm allows us to solve very high-dimensional problems that cannot be efficiently addressed with existing planners. Our experiments show nearly linear speedups with eighty processors and indicate that similar speedups can be obtained with several hundred processors.

This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampling-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.

We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner, which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.