Autonomous navigation in ice-covered waters poses significant challenges due to the frequent lack of viable collision-free trajectories. When complete obstacle avoidance is infeasible, it becomes imperative for the navigation strategy to minimize collisions. Additionally, the dynamic nature of ice, which moves in response to ship maneuvers, complicates the path planning process. To address these challenges, we propose a novel deep learning model to estimate the coarse dynamics of ice movements triggered by ship actions through occupancy estimation. To ensure real-time applicability, we propose a novel approach that caches intermediate prediction results and seamlessly integrates the predictive model into a graph search planner. We evaluate the proposed planner both in simulation and in a physical testbed against existing approaches and show that our planner significantly reduces collisions with ice when compared to the state-of-the-art. Codes and demos of this work are available at https://github.com/IvanIZ/predictive-asv-planner.

In this article, we study multirobot path planning for persistent monitoring tasks. We consider the case where robots have a limited battery capacity with a discharge time$D$. We represent the areas to be monitored as the vertices of a weighted graph. For each vertex, there is a constraint on the maximum allowable time between robot visits, called the latency. The objective is to find the minimum number of robots that can satisfy these latency constraints while also ensuring that the robots periodically charge at a recharging depot. The decision version of this problem is known to be PSPACE-complete. We present a$O\left(\frac{\log D}{\log \log D} h \log \rho\right)$approximation algorithm for the problem where$\rho$is the ratio of the maximum and the minimum latency constraints, and$h$reflects the ratio of distance of vertices from the depot to their latency constraints. We also present an orienteering-based heuristic to solve the problem and show empirically that it typically provides higher quality solutions than the approximation algorithm. We extend our results to provide an algorithm for the problem of minimizing the maximum weighted latency given a fixed number of robots. We evaluate our algorithms on large problem instances in a patrolling scenario and in a wildfire monitoring application. We also compare the algorithms with an existing solver on benchmark instances.

We study informative path planning for active regression in Gaussian Processes (GP). Here, a resource constrained robot team collects measurements of an unknown function, assumed to be a sample from a GP, with the goal of minimizing the trace of the$M$-weighted expected squared estimation error covariance (where$M$is a positive semidefinite matrix) resulting from the GP posterior mean. While greedy heuristics are a popular solution in the case of length constrained paths, it remains a challenge to computeoptimalsolutions in the discrete setting subject to routing constraints. We show that this challenge is surprisingly easy to circumvent. Using the optimality of the posterior mean for a class of functions of the squared loss yields an exact formulation as a mixed integer program. We demonstrate that this approach finds optimal solutions in a variety of settings in seconds and when terminated early, it finds sub-optimal solutions of higher quality than existing heuristics.

Adaptive task planning is fundamental to ensuring effective and seamless human-robot collaboration. This paper introduces a robot task planning framework that takes into account both human leading/following preferences and performance, specifically focusing on task allocation and scheduling in collaborative settings. We present a proactive task allocation approach with three primary objectives: enhancing team performance, incorporating human preferences, and upholding a positive human perception of the robot and the collaborative experience. Through a user study, involving an autonomous mobile manipulator robot working alongside participants in a collaborative scenario, we confirm that the task planning framework successfully attains all three intended goals, thereby contributing to the advancement of adaptive task planning in human-robot collaboration. This paper mainly focuses on the first two objectives, and we discuss the third objective, participants' perception of the robot, tasks, and collaboration in a companion paper.

Ice conditions often require ships to reduce speed and deviate from their main course to avoid damage to the ship. In addition, broken ice fields are becoming the dominant ice conditions encountered in the Arctic, where the effects of collisions with ice are highly dependent on where contact occurs and on the particular features of the ice floes. In this paper, we present AUTO-IceNav, a framework for the autonomous navigation of ships operating in ice floe fields. Trajectories are computed in a receding-horizon manner, where we frequently replan given updated ice field data. During a planning step, we assume a nominal speed that is safe with respect to the current ice conditions, and compute a reference path. We formulate a novel cost function that minimizes the kinetic energy loss of the ship from ship-ice collisions and incorporate this cost as part of our lattice-based path planner. The solution computed by the lattice planning stage is then used as an initial guess in our proposed optimization-based improvement step, producing a locally optimal path. Extensive experiments were conducted both in simulation and in a physical testbed to validate our approach.

In online peer-to-peer games, players send periodic updates to each other and each player must locally reconstruct the position of their opponents in between these updates. In scenarios where players are driving cars, high speeds produce more pronounced errors in local replication of online opponents. In this work, we propose a new method of replicating opponents with less data sent and up to 45% less error compared to the state-of-the-art. We use a neural network-based approach to predict an opponent's position, combined with a path tracking controller from the field of mobile robotics, to produce smooth, believable trajectories for opponents' vehicles. We also propose a neural network-based approach to predict a replicated opponent's trajectory following a collision with a static obstacle.

Many problems in robotics seek to simultaneously optimize several competing objectives. A conventional approach is to create a single cost function comprised of the weighted sum of the individual objectives. Solutions to this scalarized optimization problem are Pareto optimal solutions to the original multiobjective problem. However, finding an accurate representation of a Pareto front remains an important challenge. Uniformly spaced weights are often inefficient and do not provide error bounds. We address the problem of computing a finite set of weights whose optimal solutions closely approximate the solution of any other weight vector. To this end, we prove fundamental properties of the optimal cost as a function of the weight vector. We propose an algorithm that greedily adds the weight vector least-represented by the current set, and provide bounds on the regret. We extend our method to include suboptimal solvers for the scalarized optimization, and handle stochastic inputs to the planning problem. Finally, we illustrate that the proposed approach significantly outperforms baseline approaches for different robot planning problems with varying numbers of objective functions.

In this article, we propose a method to replan coverage paths for a robot operating in an environment with initially unknown static obstacles. Existing coverage approaches reduce coverage time by covering along the minimum number of coverage lines (straight-line paths). However, recomputing such paths online can be computationally expensive resulting in robot stoppages that increase coverage time. A naive alternative isgreedy detourreplanning, i.e., replanning with minimum deviation from the initial path, which is efficient to compute but may result in unnecessary detours. In this work, we propose an anytime coverage replanning approach namedOARP-Replanthat performs near-optimal replans to an interrupted coverage path within a given time budget. We do this by solving linear relaxations of integer linear programs to identify sections of the interrupted path that can be optimally replanned within the time budget. We validate OARP-Replan in simulation and perform comparisons against a greedy detour replanner and other state-of-the-art coverage planners. We also demonstrate OARP-Replan in experiments using an industrial-level autonomous robot.

Legible motion is intent-expressive, which when employed during social robot navigation, allows others to quickly infer the intended avoidance strategy. Predictable motion matches an observer's expectation which, during navigation, allows others to confidently carryout the interaction. In this work, we present a navigation framework capable of reasoning on its legibility and predictability with respect to dynamic interactions, e.g., a passing side. Our approach generalizes the previously formalized notions of legibility and predictability by allowing dynamic goal regions in order to navigate in dynamic environments. This generalization also allows us to quantitatively evaluate the legibility and the predictability of trajectories with respect to navigation interactions. Our approach is shown to promote legible behavior in ambiguous scenarios and predictable behavior in unambiguous scenarios. In a multi-agent environment, this yields an increase in safety while remaining competitive in terms of goal-efficiency when compared to other robot navigation planners in multi-agent environments. The code of this work is made publicly available1.

Human supervisors in multi-robot systems are primarily responsible for monitoring robots, but can also be assigned with secondary tasks. These tasks can act as interruptions and can be categorized as either intrinsic, i.e., being directly related to the monitoring task, or extrinsic, i.e., being unrelated. In this paper, we investigate the impact of these two types of interruptions through a user study (N = 39), where participants monitor a number of remote mobile robots while intermittently being interrupted by either a robot fault correction task (intrinsic) or a messaging task (extrinsic). We find that task performance of participants does not change significantly with the interruptions but depends greatly on the number of robots. However, interruptions result in an increase in perceived workload, and extrinsic interruptions have a more negative effect on workload across all NASA-TLX scales. Participants also reported switching between extrinsic interruptions and the primary task to be more difficult compared to the intrinsic interruption case. Statistical significance of these results is confirmed using ANOVA and one-sample t-test. These findings suggest that when deciding task assignment in such supervision systems, one should limit interruptions from secondary tasks, especially extrinsic ones, in order to limit user workload.

We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.

Vessel transit in ice-covered waters poses unique challenges in safe and efficient motion planning. When the concentration of ice is high, it may not be possible to find collision-free trajectories. Instead, ice can be pushed out of the way if it is small or if contact occurs near the edge of the ice. In this work, we propose a real-time navigation framework that minimizes collisions with ice and distance travelled by the vessel. We exploit a lattice-based planner with a cost that captures the ship interaction with ice. To address the dynamic nature of the environment, we plan motion in a receding horizon manner based on updated vessel and ice state information. Further, we present a novel planning heuristic for evaluating the cost-to-go, which is applicable to navigation in a channel without a fixed goal location. The performance of our planner is evaluated across several levels of ice concentration both in simulated and in real-world experiments.

This paper presents a solution for the problem of optimal planning for a robot in a collaborative humanrobot team, where the human supervisor is intermittently available to assist the robot in completing tasks more quickly. Specifically, we address the challenge of computing the fastest path between two configurations in an environment with time constraints on how long the robot can wait for assistance. To solve this problem, we propose a novel approach that utilizes the concepts of budget and critical departure times, which enables us to obtain optimal solution while scaling to larger problem instances than existing methods. We demonstrate the effectiveness of our approach by comparing it with several baseline algorithms on a city road network and analyzing the quality of the obtained solutions. Our work contributes to the field of robot planning by addressing a critical issue of incorporating human assistance and environmental restrictions, which has significant implications for real-world applications.

With the introduction of collaborative robots, humans and robots can now work together in close proximity and share the same workspace. However, this collaboration presents various challenges that need to be addressed to ensure seamless cooperation between the agents. This paper focuses on task planning for human-robot collaboration, taking into account the human’s performance and their preference for following or leading. Unlike conventional task allocation methods, the proposed system allows both the robot and human to select and assign tasks to each other. Our previous studies evaluated the proposed framework in a computer simulation environment. This paper extends the research by implementing the algorithm in a real scenario where a human collaborates with a Fetch mobile manipulator robot. We briefly describe the experimental setup, procedure and implementation of the planned user study. As a first step, in this paper, we report on a system evaluation study where the experimenter enacted different possible behaviours in terms of leader/follower preferences that can occur in a user study. Results show that the robot can adapt and respond appropriately to different human agent behaviours, enacted by the experimenter. A future user study will evaluate the system with human participants.

Lattice-based planning techniques simplify the motion planning problem for autonomous vehicles by limiting available motions to a pre-computed set of primitives. These primitives are combined online to generate complex maneuvers. A set of motion primitives$t$-span a lattice if, given a real number$t\geq 1$, any configuration in the lattice can be reached via a sequence of motion primitives whose cost is no more than a factor of$t$from optimal. Computing a minimal$t$-spanning set balances a trade-off between computed motion quality and motion planning performance. In this work, we formulate this problem for an arbitrary lattice as a mixed integer linear program. We also propose an A*-based algorithm to solve the motion planning problem using these primitives and an algorithm that removes the excessive oscillations from planned motions – a common problem in lattice-based planning. Our method is validated for autonomous driving in both parking lot and highway scenarios.

When a robot learns from human examples, most approaches assume that the human partner provides examples of optimal behavior. However, there are applications in which the robot learns from nonexpert humans. We argue that the robot should learn not only about the human's objectives, but also about their expertise level. The robot could then leverage this joint information to reduce or increase the frequency at which it provides assistance to its human's partner or be more cautious when learning new skills from novice users. Similarly, by taking into account the human's expertise, the robot would also be able to infer a human's true objectives even when the human fails to properly demonstrate these objectives due to a lack of expertise. In this article, we propose to jointly infer the expertise level and the objective function of a human given observations of their (possibly) nonoptimal demonstrations. Two inference approaches are proposed. In the first approach, inference is done over a finite discrete set of possible objective functions and expertise levels. In the second approach, the robot optimizes over the space of all possible hypotheses and finds the objective function and the expertise level that best explain the observed human behavior. We demonstrate our proposed approaches both in simulation and with real user data.

Planning a safe trajectory for an ego vehicle through an environment with occluded regions is a challenging task. Existing methods use some combination of metrics to evaluate a trajectory, either taking a worst case view or allowing for some probabilistic estimate, to eliminate or minimize the risk of collision respectively. Typically, these approaches assume occluded regions of the environment are unsafe and must be avoided, resulting in overly conservative trajectories-particularly when there are no hidden risks present. We propose a local trajectory planning algorithm which generates safe trajectories that maximize observations on un-certain regions. In particular, we seek to gain information on occluded areas that are most likely to pose a risk to the ego vehicle on its future path. Calculating the information gain is a computationally complex problem; our method approximates the maximum information gain and results in vehicle motion that remains safe but is less conservative than state-of-the-art approaches. We evaluate the performance of the proposed method within the CARLA simulator in different scenarios.

Recent advances in collaborative robots have provided an opportunity for the close collaboration of humans and robots in a shared workspace. To exploit this collaboration, robots need to plan for optimal team performance while considering human presence and preference. This paper studies the problem of task selection and planning in a collaborative, simulated scenario. In contrast to existing approaches, which mainly involve assigning tasks to agents by a task allocation unit and informing them through a communication interface, we give the human and robot the agency to be the leader or follower. This allows them to select their own tasks or even assign tasks to each other. We propose a task selection and planning algorithm that enables the robot to consider the human’s preference to lead, as well as the team and the human’s performance, and adapts itself accordingly by taking or giving the lead. The effectiveness of this algorithm has been validated through a simulation study with different combinations of human accuracy levels and preferences for leading.

Mobile robots are often tasked with repeatedly navigating through an environment whose traversability changes over time. These changes may exhibit some hidden structure, which can be learned. Many studies consider reactive algorithms for online planning, however, these algorithms do not take advantage of the past executions of the navigation task for future tasks. In this article, we formalize the problem of minimizing the total expected cost to perform multiple start-to-goal navigation tasks on a roadmap by introducing the learned reactive planning problem. We propose a method that captures information from past executions to learn a motion policy to handle obstacles that the robot has seen before. We propose the LAMP framework, which integrates the generated motion policy with an existing navigation stack. Finally, an extensive set of experiments in simulated and real-world environments show that the proposed method outperforms the state-of-the-art algorithms by 10% to 40% in terms of expected time to travel from start to goal. We also evaluate the robustness of the proposed method in the presence of localization and mapping errors on a real robot.

The use of collaborative robots is becoming more widespread across industries. This makes it essential to study robot planning in order to work effectively and smoothly with human teammates while maintaining a positive human perception of the robots. This paper evaluates the influence of a robot’s strategy and decision making on the participants’ perception of the robot. We designed an online experiment where a robot and participants need to collaborate and organize a set of objects. We studied three different strategies where the robot either prioritizes the human’s objective, its own objective, or uses a balanced strategy. We then analyze and report the results based on participants’ answers to questionnaires before and after the experiment, their comments, and their actions during the experiment. The results show that strategies prioritizing the human’s objective, or balancing between the robot’s and the human’s objectives can effectively improve participants’ perception of the robot and create a collaborative environment.

Enabling a broader range of users to efficiently deploy autonomous mobile robots requires intuitive frameworks for specifying a robot's task and behaviour. We present a novel approach using learning from corrections (LfC), where a user is iteratively presented with a solution to a motion planning problem. Users might have preferences about parts of a robot's environment that are suitable for robot traffic or that should be avoided as well as preferences on the control actions a robot can take. The robot is initially unaware of these preferences; thus, we ask the user to provide a correction to the presented path. We assume that the user evaluates paths based on environment and motion features. From a sequence of corrections we learn weights for these features, which are then considered by the motion planner, resulting in future paths that better fit the user's preferences. We prove completeness of our algorithm and demonstrate its performance in simulations. Thereby, we show that the learned preferences yield good results not only for a set of training tasks but also for test tasks, as well as for different types of user behaviour.

We study active preference learning as a frame-work for intuitively specifying the behaviour of autonomous robots. A user chooses the preferred behaviour from a set of alternatives, from which the robot learns the user's preferences, modeled as a parameterized cost function. Previous approaches present users with alternatives that minimize the uncertainty over the parameters of the cost function. However, different parameters might lead to the same optimal behaviour; as a consequence the solution space is more structured than the parameter space. We exploit this by proposing a query selection that greedily reduces the maximum error ratio over the solution space. In simulations we demonstrate that the proposed approach outperforms other state of the art techniques in both learning efficiency and ease of queries for the user. Finally, we show that evaluating the learning based on the similarities of solutions instead of the similarities of weights allows for better predictions for different scenarios.

This paper characterizes safe following distances for on-road driving when vehicles can avoid collisions by either braking or by swerving into an adjacent lane. In particular, we focus on safety as defined in the Responsibility-Sensitive Safety (RSS) framework. We extend RSS by introducing swerve maneuvers as a valid response in addition to the already present brake maneuver. These swerve maneuvers use the more realistic kinematic bicycle model rather than the double integrator model of RSS. We show that these swerve maneuvers allow a vehicle to safely follow a lead vehicle more closely than the RSS braking maneuvers do. The use of the kinematic bicycle model is then validated by comparing these swerve maneuvers to swerves of a dynamic single-track model. The analysis in this paper can be used to inform both offline safety validation as well as safe control and planning.

This paper focuses on the problem of deploying a set of autonomous robots to efficiently monitor multiple types of events in an environment. There is a density function over the environment for each event type representing the weighted likelihood of the event at each location. The robots are heterogeneous in that each robot is equipped with a set of sensors and it is capable of sensing a subset of event types. The objective is to deploy the robots in the environment to minimize a linear combination of the total sensing quality of the events. We propose a new formulation for the problem which is a natural extension of the homogeneous problem. We propose distributed algorithms that drive the robots to locally optimal positions in both continuous environments that are obstacle-free, and in discrete environments that may contain obstacles. In both cases we prove convergence to locally optimal positions. We provide extension to the case where the density functions are unknown prior to the deployment in continuous environments. Finally, we present benchmarking results and physical experiments to characterize the solution quality.

The ability to navigate uncertain environments from a start to a goal location is a necessity in many applications. While there are many reactive algorithms for online replanning, there has not been much investigation in leveraging past executions of the same navigation task to improve future executions. In this work, we first formalize this problem by introducing the Learned Reactive Planning Problem (LRPP). Second, we propose a method to capture these past executions and from that determine a motion policy to handle obstacles that the robot has seen before. Third, we show from our experiments that using this policy can significantly reduce the execution cost over just using reactive algorithms.

In this paper we consider the problem of computing an optimal set of motion primitives for a lattice planner. The objective we consider is to compute a minimal set of motion primitives that t-span a configuration space lattice. A set of motion primitives t-span a lattice if, given a real number t greater or equal to one, any configuration in the lattice can be reached via a sequence of motion primitives whose cost is no more than t times the cost of the optimal path to that configuration. Determining the smallest set of t-spanning motion primitives allows for quick traversal of a state lattice in the context of robotic motion planning, while maintaining a t-factor adherence to the theoretically optimal path. While several heuristics exist to determine a t-spanning set of motion primitives, these are presented without guarantees on the size of the set relative to optimal. This paper provides a proof that the minimal t-spanning control set problem for a lattice defined over an arbitrary robot configuration space is NP-complete, and presents a compact mixed integer linear programming formulation to compute an optimal t-spanner. We show that solutions obtained by the mixed integer linear program have significantly fewer motion primitives than state of the art heuristic algorithms, and out perform a set of standard primitives used in robotic path planning.

This paper introduces a method to compute a sparse lattice planner control set that is suited to a particular task by learning from a representative dataset of vehicle paths. To do this, we use a scoring measure similar to the Fréchet distance and propose an algorithm for evaluating a given control set according to the scoring measure. Control actions are then selected from a dense control set according to an objective function that rewards improvements in matching the dataset while also encouraging sparsity. This method is evaluated across several experiments involving real and synthetic datasets, and it is shown to generate smaller control sets when compared to the previous state-of-the-art lattice control set computation technique, with these smaller control sets maintaining a high degree of manoeuvrability in the required task. This results in a planning time speedup of up to 4.31x when using the learned control set over the state-of-the-art computed control set. In addition, we show the learned control sets are better able to capture the driving style of the dataset in terms of path curvature.

Estimating a user's expertise level based on observations of their actions will result in better human-robot collaboration, by enabling the robot to adjust its behaviour and the assistance it provides according to the skills of the particular user it's interacting with. This paper details an approach to incrementally and continually estimate the expertise of a user whose goal is to optimally complete a given task. The user's expertise level, here represented as a scalar parameter, is estimated by evaluating how far their actions are from optimal. The proposed approach was tested using data from an online study where participants were asked to complete various instances of a simulated kitting task. An optimal planner was used to estimate the “goodness” of all available actions at any given task state. We found that our expertise level estimates correlate strongly with observed after-task performance metrics and that it is possible to differentiate novices from experts after observing, on average, 33% of the errors made by the novices.

In this paper, we propose a new method for solving multirobot motion planning problems with complex constraints. We focus on an important class of problems that require an allocation of spatially distributed tasks to robots, along with efficient paths for each robot to visits their task locations. We introduce a framework for solving these problems that naturally couples allocation with path planning. The allocation problem is encoded as a Boolean Satisfiability problem (SAT) and the path planning problem is encoded as a traveling salesman problem (TSP). In addition, the framework can handle complex constraints such as battery life limitations, robot carrying capacities, and robot-task incompatibilities. We propose an algorithm that leverages recent advances in Satisfiability Modulo Theory (SMT) to combine state-of-the-art SAT and TSP solvers. We characterize the correctness of our algorithm and evaluate it in simulation on a series of patrolling, periodic routing, and multirobot sample collection problems. The results show our algorithm significantly outperforms state-of-the-art mathematical programming solvers.

This paper focuses on the problem of deploying a set of autonomous robots to efficiently service tasks that arrive sequentially in an environment over time. Each task is serviced when the robot visits the corresponding task location. Robots can then redeploy while waiting for the next task to arrive. The objective is to redeploy the robots taking into account the next N task arrivals. We seek to minimize a linear combination of the expected cost to service tasks and the redeployment cost between task arrivals. In the single robot case, we propose a one-stage greedy algorithm and prove its optimality. For multiple robots, the problem is NP-hard, and we propose two constant-factor approximation algorithm, one for the problem with a horizon of two task arrivals and the other for the infinite horizon when redeployment cost is weighted more heavily than service cost. Finally, we present extensive benchmarking results to characterize both solution quality and runtime.

In this paper we develop an approach for learning user preferences for complex task specifications through human-robot interaction. We consider the problem of planning robot motion in a known environment, but where a user has specified additional spatial and temporal constraints on allowable robot motions. To illustrate the impact of the user's constraints on performance, we iteratively present users with alternative solutions on an interface. The user provides a ranking of alternate paths, and from this we learn about the importance of different constraints. This allows for an accessible method for specifying complex robot tasks. We present an algorithm that iteratively builds a set of constraints on the relative importance of each user constraint, and prove that with sufficient interaction, the algorithm determines a user-optimal path. We demonstrate the practical performance by simulating realistic material transport scenarios in industrial facilities.

As robots' capability and autonomy improve, they are expected to increasingly operate in human environments, and interact with novice, untrained users. When robots operate in human or shared environments, their tasks and behaviours need to be specified; this task is typically performed by a human operator or supervisor. The human operator may specify constraints on robot behaviour to make the robot more predictable or align its behaviour with user expectations. However, these constraints may impact robot task performance. This paper investigates how novice users generate robot specifications and proposes metrics for quantifying specification quality. The proposed approach is evaluated with a user study, where novice users provide specifications for an autonomous robot operating in a shared warehouse environment. We find that untrained users create a wide variety of behaviour-limiting specifications, that users generally have difficulty creating efficient specifications, and that they were not able to correctly assess their own performance.

The Sat-Tsp language was recently proposed [1] for expressing and solving high-level robotic path planning problems. In this paper we show how different constraints that commonly appear in path planning problems, such as set constraints, counting constraints, and ordering constraints can all be expressed in the Sat-Tsp language. We also show how the language can be used to express multi-robot path planning problems. We evaluate our existing solver approaches on test problems that include a variety of complex constraints and we demonstrate the language through a ROS implementation. We also provide a new approach that reduces the Sat-Tsp language to the generalized traveling salesman problem language. We show that this new approach outperforms our existing approaches on problems that contain one-on-a-set constraints.

This paper addresses the task scheduling and path planning problem for a team of cooperating vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two vehicles with complementary capabilities, a truck restricted to travel along a street network, and a quadrotor micro-aerial vehicle of capacity one that can be deployed from the truck to perform deliveries. The problem is formulated as an optimal path planning problem on a graph and the goal is to find the shortest cooperative route enabling the quadrotor to deliver items at all requested locations. The problem is shown to be NP-hard. A solution is then proposed using a novel reduction to the Generalized Traveling Salesman Problem, for which well-established heuristic solvers exist. The heterogeneous delivery problem contains as a special case the problem of scheduling deliveries from multiple static warehouses. We propose two additional algorithms, based on enumeration and a reduction to the traveling salesman problem, for this special case. Simulation results compare the performance of the presented algorithms and demonstrate examples of delivery route computations over real urban street maps.

This paper addresses a multirobot scheduling problem in which autonomous unmanned aerial vehicles (UAVs) must be recharged during a long-term mission. The proposal is to introduce a separate team of dedicated charging robots that the UAVs can dock with in order to recharge. The goal is to schedule and plan minimum cost paths for charging robots such that they rendezvous with and replenish the UAVs, as needed, during the mission. The approach is to discretize the 3-D UAV flight trajectories into sets of projected charging points on the ground, thus allowing the problem to be abstracted onto a partitioned graph. Solutions consist of charging robot paths that collectively charge each of the UAVs. The problem is solved by first formulating the rendezvous planning problem to recharge each UAV once using both an integer linear program and a transformation to the Travelling Salesman Problem. The methods are then leveraged to plan recurring rendezvous' over longer horizons using fixed horizon and receding horizon strategies. Simulation results using realistic vehicle and battery models demonstrate the feasibility and robustness of the proposed approach.

In this paper we introduce a new language in which discrete path planning problems for mobile robots can be specified and solved. Given an environment represented as a graph and a Boolean variable for each vertex to represent its inclusion/exclusion on the path, we consider the problem of finding the shortest path (or tour) in the graph subject to a Boolean satisfiability (Sat) formula defined over the vertex variables. We call this problem Sat-Tsp. We show the expressiveness of this language for specifying complex motion planning objectives in a discrete environment. We then present three solution techniques for this problem, including a novel reduction to the well known travelling salesman problem (Tsp). We present extensive simulation results which compare the performance of the three solvers on standard benchmarks from Tsp, Sat, and Generalized Tsp (Gtsp) literature.

We consider the problem of dynamic vehicle routing under exact-time constraints on servicing demands. Demands are sequentially generated in an environment, and every demand needs to be serviced exactly after a fixed finite interval of time after it is generated. We design routing policies for a service vehicle to maximize the fraction of demands serviced at steady state. The main contributions are as follows. First, we demonstrate that this problem is described by an appropriate directed acyclic graph structure which leads to a computationally efficient routing algorithm based on a longest-path computation. Second, under the assumption of the demands being generated uniformly randomly in the environment and via a Poisson process in time, we provide two analytic lower bounds on the service fraction of the longest path policy. The first bound is relative to an optimal noncausal version of the policy, i.e., a policy based on knowledge of all future demand requests. The second bound is an explicit function of the vehicle dynamics and demand generation rate and, therefore, useful as a design tool. Finally, we present numerical results to support the analytic bounds.

This paper addresses the problem of maintaining persistence in coordinated tasks performed by a team of autonomous robots. We introduce a dedicated team of charging robots to service a team of primary working robots. Given that the trajectories of the working robots are known within a planning interval, the objective is to plan routes for the charging robots such that they rendezvous with and recharge all working robots to guarantee their continuous operation. To this end, the working robot trajectories are discretized to form a finite set of recharging points at which rendezvous can occur. The problem is formulated as a directed acyclic graph with vertex partitions containing sets of charging points for each working robot. Solutions consist of paths through the graph for each of the charging robots. The problem is shown to be NP-hard and a mixed integer linear program formulation is presented and solved for small problem instances. Finally, it is shown that while the optimal solution is not computationally feasible for large problem sizes, it is possible to graphically transform the single charging robot problem to a Traveling Salesman Problem, for which existing heuristic and approximation algorithms can be applied. Simulation results are presented for both single and multiple charging robot scenarios.

In this paper we present a method for automatically planning robust optimal paths for a group of robots that satisfy a common high level mission specification. Each robot's motion in the environment is modeled as a weighted transition system, and the mission is given as a Linear Temporal Logic (LTL) formula over a set of propositions satisfied by the regions of the environment. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize the maximum time between satisfying instances of the optimizing proposition while ensuring that the LTL formula is satisfied even with uncertainty in the robots' traveling times. We characterize a class of LTL formulas that are robust to robot timing errors, for which we generate optimal paths if no timing errors are present, and we present bounds on the deviation from the optimal values in the presence of errors. We implement and experimentally evaluate our method considering a persistent monitoring task in a road network environment.

In this paper, we present controllers that enable mobile robots to persistently monitor or sweep a changing environment. The environment is modeled as a field that is defined over a finite set of locations. The field grows linearly at locations that are not within the range of a robot and decreases linearly at locations that are within range of a robot. We assume that the robots travel on given closed paths. The speed of each robot along its path is controlled to prevent the field from growing unbounded at any location. We consider the space of speed controllers that are parametrized by a finite set of basis functions. For a single robot, we develop a linear program that computes a speed controller in this space to keep the field bounded, if such a controller exists. Another linear program is derived to compute the speed controller that minimizes the maximum field value over the environment. We extend our linear program formulation to develop a multirobot controller that keeps the field bounded. We characterize, both theoretically and in simulation, the robustness of the controllers to modeling errors and to stochasticity in the environment.

This paper presents controllers that enable a mobile robot to persistently monitor or sweep a changing environment. The changing environment is modeled as an accumulation function which grows in areas that are not within range of the robot, and decreases in areas that are within range of the robot. The robot must continually move through the environment to prevent the accumulation of any area from growing unbounded. We consider the case in which a predefined path is given for the robot, and we focus on controlling the robot's speed along the path. We characterize necessary and sufficient conditions on the speed controller of the robot for keeping the accumulation function bounded. We then search among the space of speed controllers that are parametrized by a finite set of basis functions. We develop a linear program to compute the optimal speed controller; that which minimizes the accumulation over the environment. Simulation results illustrate the performance of the controllers.

This paper proposes a path planning algorithm and a velocity control algorithm for underwater gliders to persistently monitor a patch of ocean. The algorithms address a pressing need among ocean scientists to collect high-value data for studying ocean events of scientific and environmental interest, such as the occurrence of harmful algal blooms. The path planner optimizes a cost function that blends two competing factors: it maximizes the information value of the path, while minimizing the deviation from the path due to ocean currents. The speed control algorithm then optimizes the speed along the planned path so that higher resolution samples are collected in areas of higher information value. The resulting paths are closed circuits that can be repeatedly traversed to collect long term ocean data in dynamic environments. The algorithms were tested during sea trials on an underwater glider operating off the coast of southern California over the course of several weeks. The results show significant improvements in data resolution and path reliability compared to a sampling path that is typically used in the region.

Persistent robot tasks such as monitoring and cleaning are concerned with controlling mobile robots to act in a changing environment in a way that guarantees that the uncertainty in the system (due to change and to the actions of the robot) remains bounded for all time. Prior work in persistent robot tasks considered only robot systems with collision-free paths that move following speed controllers. In this paper we describe a solution to multi-robot persistent monitoring, where robots have intersecting trajectories. We develop collision and deadlock avoidance algorithms that are based on stopping policies, and quantify the impact of the stopping times on the overall stability of the speed controllers.

In this paper we present a method for automatically planning optimal paths for a group of robots that satisfy a common high level mission specification. Each robot's motion in the environment is modeled as a weighted transition system. The mission is given as a Linear Temporal Logic formula. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize the maximum time between satisfying instances of the optimizing proposition. Our method is guaranteed to compute an optimal set of robot paths. We utilize a timed automaton representation in order to capture the relative position of the robots in the environment. We then obtain a bisimulation of this timed automaton as a finite transition system that captures the joint behavior of the robots and apply our earlier algorithm for the single robot case to optimize the group motion. We present a simulation of a persistent monitoring task in a road network environment.

Recent years have witnessed great advancements in the science and technology of autonomy, robotics, and networking. This paper surveys recent concepts and algorithms for dynamic vehicle routing (DVR), that is, for the automatic planning of optimal multivehicle routes to perform tasks that are generated over time by an exogenous process. We consider a rich variety of scenarios relevant for robotic applications. We begin by reviewing the basic DVR problem: demands for service arrive at random locations at random times and a vehicle travels to provide on-site service while minimizing the expected wait time of the demands. Next, we treat different multivehicle scenarios based on different models for demands (e.g., demands with different priority levels and impatient demands), vehicles (e.g., motion constraints, communication, and sensing capabilities), and tasks. The performance criterion used in these scenarios is either the expected wait time of the demands or the fraction of demands serviced successfully. In each specific DVR scenario, we adopt a rigorous technical approach that relies upon methods from queueing theory, combinatorial optimization, and stochastic geometry. First, we establish fundamental limits on the achievable performance, including limits on stability and quality of service. Second, we design algorithms, and provide provable guarantees on their performance with respect to the fundamental limits.

In this paper we present a method for automatically generating optimal robot trajectories satisfying high level mission specifications. The motion of the robot in the environment is modeled as a weighted transition system. The mission is specified by a general linear temporal logic formula. In addition, we require that an optimizing proposition must be repeatedly satisfied. The cost function that we seek to minimize is the maximum time between satisfying instances of the optimizing proposition. For every environment model, and for every formula, our method computes a robot trajectory which minimizes the cost function. The problem is motivated by robotic monitoring and data gathering. In this setting, the optimizing proposition is satisfied at locations where data can be uploaded, and the formula specifies a an infinite horizon data collection mission. Our method utilizes Büchi automata to produce an automaton (which can be thought of as a graph) whose runs satisfy the temporal logic formula. We then present a graph algorithm which computes a path corresponding to the optimal robot trajectory. We also present an implementation for a robot performing a data gathering mission.