Stephen L. Smith

Xu Chu Ding, Stephen L. Smith, Calin Belta et al.

We present a method to generate a robot control strategy that maximizes the probability to accomplish a task. The task is given as a Linear Temporal Logic (LTL) formula over a set of properties that can be satisfied at the regions of a partitioned environment. We assume that the probabilities with which the properties are satisfied at the regions are known, and the robot can determine the truth value of a proposition only at the current region. Motivated by several results on partitioned-based abstractions, we assume that the motion is performed on a graph. To account for noisy sensors and actuators, we assume that a control action enables several transitions with known probabilities. We show that this problem can be reduced to the problem of generating a control policy for a Markov Decision Process (MDP) such that the probability of satisfying an LTL formula over its states is maximized. We provide a complete solution for the latter problem that builds on existing results from probabilistic model checking. We include an illustrative case study.

Xu Chu Ding, Stephen L. Smith, Calin Belta et al.

In this paper, we develop a method to automatically generate a control policy for a dynamical system modeled as a Markov Decision Process (MDP). The control specification is given as a Linear Temporal Logic (LTL) formula over a set of propositions defined on the states of the MDP. We synthesize a control policy such that the MDP satisfies the given specification almost surely, if such a policy exists. In addition, we designate an "optimizing proposition" to be repeatedly satisfied, and we formulate a novel optimization criterion in terms of minimizing the expected cost in between satisfactions of this proposition. We propose a sufficient condition for a policy to be optimal, and develop a dynamic programming algorithm that synthesizes a policy that is optimal under some conditions, and sub-optimal otherwise. This problem is motivated by robotic applications requiring persistent tasks, such as environmental monitoring or data gathering, to be performed.

Steven Caro, Stephen L. Smith

Nonprehensile manipulation, such as pushing objects across cluttered environments, presents a challenging control problem due to complex contact dynamics and long-horizon planning requirements. In this work, we propose HeRD, a hierarchical reinforcement learning-diffusion policy that decomposes pushing tasks into two levels: high-level goal selection and low-level trajectory generation. We employ a high-level reinforcement learning (RL) agent to select intermediate spatial goals, and a low-level goal-conditioned diffusion model to generate feasible, efficient trajectories to reach them. This architecture combines the long-term reward maximizing behaviour of RL with the generative capabilities of diffusion models. We evaluate our method in a 2D simulation environment and show that it outperforms the state-of-the-art baseline in success rate, path efficiency, and generalization across multiple environment configurations. Our results suggest that hierarchical control with generative low-level planning is a promising direction for scalable, goal-directed nonprehensile manipulation. Code, documentation, and trained models are available: https://github.com/carosteven/HeRD.

Stephen Smith, Qing Zhou

Learning the structure of causal directed acyclic graphs (DAGs) is useful in many areas of machine learning and artificial intelligence, with wide applications. However, in the high-dimensional setting, it is challenging to obtain good empirical and theoretical results without strong and often restrictive assumptions. Additionally, it is questionable whether all of the variables purported to be included in the network are observable. It is of interest then to restrict consideration to a subset of the variables for relevant and reliable inferences. In fact, researchers in various disciplines can usually select a set of target nodes in the network for causal discovery. This paper develops a new constraint-based method for estimating the local structure around multiple user-specified target nodes, enabling coordination in structure learning between neighborhoods. Our method facilitates causal discovery without learning the entire DAG structure. We establish consistency results for our algorithm with respect to the local neighborhood structure of the target nodes in the true graph. Experimental results on synthetic and real-world data show that our algorithm is more accurate in learning the neighborhood structures with much less computational cost than standard methods that estimate the entire DAG. An R package implementing our methods may be accessed at https://github.com/stephenvsmith/CML.

Shamak Dutta, Nils Wilde, Stephen L. Smith

In this paper, we consider a subset selection problem in a spatial field where we seek to find a set of k locations whose observations provide the best estimate of the field value at a finite set of prediction locations. The measurements can be taken at any location in the continuous field, and the covariance between the field values at different points is given by the widely used squared exponential covariance function. One approach for observation selection is to perform a grid discretization of the space and obtain an approximate solution using the greedy algorithm. The solution quality improves with a finer grid resolution but at the cost of increased computation. We propose a method to reduce the computational complexity, or conversely to increase solution quality, of the greedy algorithm by considering a search space consisting only of prediction locations and centroids of cliques formed by the prediction locations. We demonstrate the effectiveness of our proposed approach in simulation, both in terms of solution quality and runtime.

Nils Wilde, Armin Sadeghi, Stephen L. Smith

In this paper, we study the well-known team orienteering problem where a fleet of robots collects rewards by visiting locations. Usually, the rewards are assumed to be known to the robots; however, in applications such as environmental monitoring or scene reconstruction, the rewards are often subjective and specifying them is challenging. We propose a framework to learn the unknown preferences of the user by presenting alternative solutions to them, and the user provides a ranking on the proposed alternative solutions. We consider the two cases for the user: 1) a deterministic user which provides the optimal ranking for the alternative solutions, and 2) a noisy user which provides the optimal ranking according to an unknown probability distribution. For the deterministic user we propose a framework to minimize a bound on the maximum deviation from the optimal solution, namely regret. We adapt the approach to capture the noisy user and minimize the expected regret. Finally, we demonstrate the importance of learning user preferences and the performance of the proposed methods in an extensive set of experimental results using real world datasets for environmental monitoring problems.

Abhinav Dahiya, Nima Akbarzadeh, Aditya Mahajan et al.

In this paper, we consider the problem of allocating human operators in a system with multiple semi-autonomous robots. Each robot is required to perform an independent sequence of tasks, subjected to a chance of failing and getting stuck in a fault state at every task. If and when required, a human operator can assist or teleoperate a robot. Conventional MDP techniques used to solve such problems face scalability issues due to exponential growth of state and action spaces with the number of robots and operators. In this paper we derive conditions under which the operator allocation problem is indexable, enabling the use of the Whittle index heuristic. The conditions can be easily checked to verify indexability, and we show that they hold for a wide range of problems of interest. Our key insight is to leverage the structure of the value function of individual robots, resulting in conditions that can be verified separately for each state of each robot. We apply these conditions to two types of transitions commonly seen in remote robot supervision systems. Through numerical simulations, we demonstrate the efficacy of Whittle index policy as a near-optimal and scalable approach that outperforms existing scalable methods.

Nils Wilde, Erdem Bıyık, Dorsa Sadigh et al.

Today's robots are increasingly interacting with people and need to efficiently learn inexperienced user's preferences. A common framework is to iteratively query the user about which of two presented robot trajectories they prefer. While this minimizes the users effort, a strict choice does not yield any information on how much one trajectory is preferred. We propose scale feedback, where the user utilizes a slider to give more nuanced information. We introduce a probabilistic model on how users would provide feedback and derive a learning framework for the robot. We demonstrate the performance benefit of slider feedback in simulations, and validate our approach in two user studies suggesting that scale feedback enables more effective learning in practice.

Megnath Ramesh, Frank Imeson, Baris Fidan et al.

In this paper, we tackle the problem of planning an optimal coverage path for a robot operating indoors. Many existing approaches attempt to discourage turns in the path by covering the environment along the least number of coverage lines, i.e., straight-line paths. This is because turning not only slows down the robot but also negatively affects the quality of coverage, e.g., tools like cameras and cleaning attachments commonly have poor performance around turns. The problem of minimizing coverage lines however is typically solved using heuristics that do not guarantee optimality. In this work, we propose a turn-minimizing coverage planning method that computes the optimal number of axis-parallel (horizontal/vertical) coverage lines for the environment in polynomial time. We do this by formulating a linear program (LP) that optimally partitions the environment into axis-parallel ranks (non-intersecting rectangles of width equal to the tool width). We then generate coverage paths for a set of real-world indoor environments and compare the results with state-of-the-art coverage approaches.

Alexander Botros, Stephen L. Smith

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 then combined online to generate more complex maneuvers. A set of motion primitives t-span a lattice if, given a real number t at least 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. Finally, we present 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.

Alexander Botros, Stephen L. Smith

Trajectory planning is commonly used as part of a local planner in autonomous driving. This paper considers the problem of planning a continuous-curvature-rate trajectory between fixed start and goal states that minimizes a tunable trade-off between passenger comfort and travel time. The problem is an instance of infinite dimensional optimization over two continuous functions: a path, and a velocity profile. We propose a simplification of this problem that facilitates the discretization of both functions. This paper also proposes a method to quickly generate minimal-length paths between start and goal states based on a single tuning parameter: the second derivative of curvature. Furthermore, we discretize the set of velocity profiles along a given path into a selection of acceleration way-points along the path. Gradient-descent is then employed to minimize cost over feasible choices of the second derivative of curvature, and acceleration way-points, resulting in a method that repeatedly solves the path and velocity profiles in an iterative fashion. Numerical examples are provided to illustrate the benefits of the proposed methods.

Florence Tsang, Tristan Walker, Ryan A. MacDonald et al.

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 paper, 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.

Pamela Carreno-Medrano, Stephen L. Smith, Dana Kulic

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 non-expert 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 of inferring a human's true objectives even when the human's fails to properly demonstrate these objectives due to a lack of expertise. In this paper, we propose to jointly infer the expertise level and objective function of a human given observations of their (possibly) non-optimal 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 expertise level that best explain the observed human behavior. We demonstrate our proposed approaches both in simulation and with real user data.

Nils Wilde, Dana Kulic, Stephen L. Smith

We study active preference learning as a framework for intuitively specifying the behaviour of autonomous robots. In active preference learning, 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.

Chuanzheng Wang, Yinan Li, Stephen L. Smith et al.

In this paper, we propose a model-free reinforcement learning method to synthesize control policies for motion planning problems with continuous states and actions. The robot is modelled as a labeled discrete-time Markov decision process (MDP) with continuous state and action spaces. Linear temporal logics (LTL) are used to specify high-level tasks. We then train deep neural networks to approximate the value function and policy using an actor-critic reinforcement learning method. The LTL specification is converted into an annotated limit-deterministic Büchi automaton (LDBA) for continuously shaping the reward so that dense rewards are available during training. A naïve way of solving a motion planning problem with LTL specifications using reinforcement learning is to sample a trajectory and then assign a high reward for training if the trajectory satisfies the entire LTL formula. However, the sampling complexity needed to find such a trajectory is too high when we have a complex LTL formula for continuous state and action spaces. As a result, it is very unlikely that we get enough reward for training if all sample trajectories start from the initial state in the automata. In this paper, we propose a method that samples not only an initial state from the state space, but also an arbitrary state in the automata at the beginning of each training episode. We test our algorithm in simulation using a car-like robot and find out that our method can learn policies for different working configurations and LTL specifications successfully.

Ryan De Iaco, Stephen L. Smith, Krzysztof Czarnecki

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 manoeuvres as a valid response in addition to the already present brake manoeuvre. These swerve manoeuvres use the more realistic kinematic bicycle model rather than the double integrator model of RSS. When vehicles are able to swerve and brake, it is shown that their required safe following distance at higher speeds is less than that required through braking alone. In addition, when all vehicles follow this new distance, they are provably safe. The use of the kinematic bicycle model is then validated by comparing these swerve manoeuvres to that of a dynamic single-track model.

Barry Gilhuly, Stephen L. Smith

In this paper we investigate the problem of using a UAV to provide current map information of the environment in front of a moving ground vehicle. We propose a simple coverage plan called a conformal lawn mower plan that enables a UAV to scan the route ahead of the ground vehicle. The plan requires only limited knowledge of the ground vehicle's future path. For a class of curvature-constrained ground vehicle paths, we show that the proposed plan requires a UAV velocity that is no more than twice the velocity required to cover the optimal plan. We also establish necessary and sufficient UAV velocities, relative to the ground vehicle velocity, required to successfully cover any path in the curvature restricted set. In simulation, we validate the proposed plan, showing that the required velocity to provide coverage is strongly related to the curvature of the ground vehicle's path. Our results also illustrate the relationship between mapping requirements and the relative velocities of the UAV and ground vehicle.

Ahmad Bilal Asghar, Stephen L. Smith, Shreyas Sundaram

In this paper we study a multi-robot path planning problem for persistent monitoring of an environment. We represent the areas to be monitored as the vertices of a weighted graph. For each vertex, there is a constraint on the maximum time spent by the robots between visits to that vertex, called the latency, and the objective is to find the minimum number of robots that can satisfy these latency constraints. The decision version of this problem is known to be PSPACE-complete. We present a $O(\log ρ)$ approximation algorithm for the problem where $ρ$ is the ratio of the maximum and the minimum latency constraints. We also present an orienteering based heuristic to solve the problem and show through simulations that in most of the cases the heuristic algorithm gives better solutions than the approximation algorithm. We evaluate our algorithms on large problem instances in a patrolling scenario and in a persistent scene reconstruction application. We also compare the algorithms with an existing solver on benchmark instances.

Ryan De Iaco, Stephen L. Smith, Krzysztof Czarnecki

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.

Frank Imeson, Stephen L. Smith

In this paper we consider discrete robot path planning problems on metric graphs. We propose a clustering method, Gamma-Clustering for the planning graph that significantly reduces the number of feasible solutions, yet retains a solution within a constant factor of the optimal. By increasing the input parameter Gamma, the constant factor can be decreased, but with less reduction in the search space. We provide a simple polynomial- time algorithm for finding optimal Gamma-Clusters, and show that for a given Gamma, this optimal is unique. We demonstrate the effectiveness of the clustering method on traveling salesman instances, showing that for many instances we obtain significant reductions in computation time with little to no reduction in solution quality.

Armin Sadeghi, Stephen L. Smith

In this paper, we address the problem of computing optimal paths through three consecutive points for the curvature-constrained forward moving Dubins vehicle. Given initial and final configurations of the Dubins vehicle, and a midpoint with an unconstrained heading, the objective is to compute the midpoint heading that minimizes the total Dubins path length. We provide a novel geometrical analysis of the optimal path, and establish new properties of the optimal Dubins' path through three points. We then show how our method can be used to quickly refine Dubins TSP tours produced using state-of-the-art techniques. We also provide extensive simulation results showing the improvement of the proposed approach in both runtime and solution quality over the conventional method of uniform discretization of the heading at the mid-point, followed by solving the minimum Dubins path for each discrete heading.

Ahmad Bilal Asghar, Stephen L. Smith

In this paper we consider a robot patrolling problem in which events arrive randomly over time at the vertices of a graph. When an event arrives it remains active for a random amount of time. If that time active exceeds a certain threshold, then we say that the event is a true event; otherwise it is a false event. The robot(s) can traverse the graph to detect newly arrived events, and can revisit these events in order to classify them as true or false. The goal is to plan robot paths that maximize the number of events that are correctly classified, with the constraint that there are no false positives. We show that the offline version of this problem is NP-hard. We then consider a simple patrolling policy based on the traveling salesman tour, and characterize the probability of correctly classifying an event. We investigate the problem when multiple robots follow the same path, and we derive the optimal (and not necessarily uniform) spacing between robots on the path.

Alphan Ulusoy, Stephen L. Smith, Calin Belta

In this paper, we consider the automated planning of optimal paths for a robotic team satisfying a high level mission specification. Each robot in the team is modeled as a weighted transition system where the weights have associated deviation values that capture the non-determinism in the traveling times of the robot during its deployment. The mission is given as a Linear Temporal Logic (LTL) formula over a set of propositions satisfied at the regions of the environment. Additionally, we have an optimizing proposition capturing some particular task that must be repeatedly completed by the team. The goal is to minimize the maximum time between successive satisfying instances of the optimizing proposition while guaranteeing that the mission is satisfied even under non-deterministic traveling times. Our method relies on the communication capabilities of the robots to guarantee correctness and maintain performance during deployment. After computing a set of optimal satisfying paths for the members of the team, we also compute a set of synchronization sequences for each robot to ensure that the LTL formula is never violated during deployment. We implement and experimentally evaluate our method considering a persistent monitoring task in a road network environment.

Alphan Ulusoy, Stephen L. Smith, Xu Chu Ding et al.

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.