Emergency departments (EDs) are fast-paced, dynamic, safety-critical spaces where clinicians are overworked and underpaid. To support clinicians, researchers are exploring the contextualization and development of clinically assistive robots (CARs) that can assume non-critical tasks to reduce clinician overload. In this article, we introduce Clinically Assistive Robot System for Emergency Medicine (CAR-EM), collaboratively developed with ED clinicians. CAR-EM includes an autonomous robot and a task specification interface. It completes tasks by leveraging control synthesis, a framework that automatically transforms high-level tasks into control while providing guarantees and feedback. We conducted a feasibility study across two different hospital EDs, where interprofessional clinicians tasked the robot to perform patient assessments and item deliveries. Clinicians found the system easy to use, and particularly helpful to offload busywork. This work demonstrates control synthesis as a feasible tool to develop autonomy for robots in safety-critical spaces, and identifies considerations for failure interventions. We also discuss ethical considerations for deploying robots in hospitals, including healthcare worker displacement and work disruption. Thus, our work: (1) highlights the unique requirements of situating robots in real world hospital EDs, and (2) demonstrates a novel approach leveraging guarantees and feedback from control synthesis methods to successfully implement context-specific CAR behaviors. Through this work, we aim to further research for safer and more reliable robots in real world, uncertain environments.

We propose an integrated planning framework for quadrupedal locomotion over dynamically changing, unforeseen terrains. Existing approaches either rely on heuristics for instantaneous foothold selection–compromising safety and versatility–or solve expensive trajectory optimization problems with complex terrain features and long time horizons. In contrast, our framework leverages reactive synthesis to generate correct-by-construction controllers at the symbolic level, and mixed-integer convex programming (MICP) for dynamic and physically feasible footstep planning for each symbolic transition. We use a high-level manager to reduce the large state space in synthesis by incorporating local environment information, improving synthesis scalability. To handle specifications that cannot be met due to dynamic infeasibility, and to minimize costly MICP solves, we leverage a symbolic repair process to generate only necessary symbolic transitions. During online execution, re-running the MICP with real-world terrain data, along with runtime symbolic repair, bridges the gap between offline synthesis and online execution. We demonstrate, in simulation, our framework’s capabilities to discover missing locomotion skills and react promptly in safety-critical environments, such as scattered stepping stones and rebars.

In this work, we examine robots "asking for help" in unpredictable human spaces. We focus on an open question particularly relevant for robots deployed in public–"how do people help robots?" We present an elicitation study that shows how asking for help in a real-world field study yields valuable and sometimes unexpected information. From our study, we examine strangers’ responses toward a robot asking for spatial directions and extract valuable themes that can inform future asking-for-help systems. Our analysis provides a wide range of information, from geometric and topological information in natural language to details about rejection during an interaction. Further, we also provide anecdotes of valuable outlier behavior that can only be captured through a study in a real public space. Through our work, we highlight the importance of in-the-wild studies and discuss how the rich information they contribute will help robots effectively ask for help.

We present a decentralized control algorithm for a robotic swarm given the task of encapsulating static and moving targets in a bounded unknown environment. We consider minimalist robots without memory, explicit communication, or localization information. The state-of-the-art approaches generally assume that the robots in the swarm are able to detect the relative position of neighboring robots and targets in order to provide convergence guarantees. In this work, we propose a novel control law for the guaranteed encapsulation of static and moving targets while avoiding all collisions, when the robots do not know the exact relative location of any robot or target in the environment. We make use of the Lyapunov stability theory to prove the convergence of our control algorithm and provide bounds on the ratio between the target and robot speeds. Furthermore, our proposed approach is able to provide stochastic guarantees under the bounds that we determine on task parameters for scenarios where a target moves faster than a robot. Finally, we present an analysis of how the emergent behavior changes with different parameters of the task and noisy sensor readings.

Robots have the potential to assist in emergency evacuation tasks, but it is not clear how robots should behave to evacuate people who are not fully compliant, perhaps due to panic or other priorities in an emergency. In this paper, we compare two robot strategies: an actively nudging robot that initiates evacuation and pulls toward the exit and a passively waiting robot that stays around users and waits for instruction. Both strategies were automatically synthesized from a description of the desired behavior. We conduct a within participant study ( = 20) in a simulated environment to compare the evacuation effectiveness between the two robot strategies. Our results indicate an advantage of the nudging robot for effective evacuation when being exposed to the evacuation scenario for the first time. The waiting robot results in lower efficiency, higher mental load, and more physical conflicts. However, participants like the waiting robots equally or slightly more when they repeat the evacuation scenario and are more familiar with the situation. Our qualitative analysis of the participants' feedback suggests several design implications for future emergency evacuation robots.

We present a method for calculating the probability that a robot successfully performs a task described using Signal Temporal Logic (STL). We focus on cases where the failure probability is very small, hence a traditional Monte-Carlo method becomes inefficient due to the large number of samples required to observe failures. Using elliptical sliced sampling, normalizing flows, and Bayesian optimization, we develop an algorithm that, under mild assumptions, is applicable to black-box systems, and can be applied to uncertainty sources with non-Gaussian probabilities. We demonstrate the application of our method on three different simulated robots.

A typical approach to creating complex robot behaviors is to compose atomic controllers, or skills, such that the resulting behavior satisfies a high-level task; however, when a task cannot be accomplished with a given set of skills, it is difficult to know how to modify the skills to make the task possible. We present a method for combining symbolic repair with physical feasibility checking and implementation to automatically modify existing skills such that the robot can execute a previously infeasible task. We encode robot skills in linear temporal logic (LTL) formulas that capture both safety constraints and goals for reactive tasks. Furthermore, our encoding captures the full skill execution, as opposed to prior work where only the state of the world before and after the skill is executed are considered. Our repair algorithm suggests symbolic modifications, then attempts to physically implement the suggestions by modifying the original skills subject to Linear Temporal Logic (LTL) constraints derived from the symbolic repair. If skills are not physically possible, we automatically provide additional constraints for the symbolic repair. We demonstrate our approach with a Baxter and a Clearpath Jackal.

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

Autonomous robots typically incorporate complex sensors in their decision-making and control loops. These sensors, such as cameras and lidars, have imperfections in their sensing and are influenced by environmental conditions. In this paper, we present a method for probabilistic verification of linearizable systems with Gaussian and Gaussian mixture noise models (e.g. from perception modules, machine learning components). We compute the probabilities of task satisfaction under Signal Temporal Logic (STL) specifications, using its robustness semantics, with a Markov Chain Monte-Carlo slice sampler. As opposed to other techniques, our method avoids over-approximations and double-counting of failure events. Central to our approach is a method for efficient and rejection-free sampling of signals from a Gaussian distribution that satisfy or violate a given STL formula. We show illustrative examples from applications in robot motion planning.

Given a heterogeneous group of robots executing a complex task represented in Linear Temporal Logic, and a new set of tasks for the group, we define the task update problem and propose a framework for automatically updating individual robot tasks given their respective existing tasks and capabilities. Our heuristic, token-based, conflict resolution task allocation algorithm generates a near-optimal assignment for the new task. We demonstrate the scalability of our approach through simulations of multi-robot tasks.

We develop a method for synthesizing control policies for stochastic, linear, time-varying systems that must perform tasks specified in signal temporal logic. We build upon an efficient, sampling-based framework that computes the probability of the system satisfying its specification. By exploiting the properties of linear systems and robustness score in temporal logic specifications, we obtain sample-efficient gradients of the satisfaction probability with respect to con-troller parameters. Therefore, by applying gradient descent we obtain locally optimized controllers that maximize the chances of satisfying the specification. We demonstrate our approach through examples of a mobile robot and a mobile manipulator in simulation.

We propose a decentralized control algorithm for a minimalistic robotic swarm with limited capabilities such that the desired global behavior emerges. We consider the problem of searching for and encapsulating various targets present in the environment while avoiding collisions with both static and dynamic obstacles. The novelty of this work is the guaranteed generation of desired complex swarm behavior with constrained individual robots which have no memory, no localization, and no knowledge of the exact relative locations of their neighbors. Moreover, we analyze how the emergent behavior changes with different parameters of the task, noise in the sensor reading, and asynchronous execution.

We develop and evaluate two human-robot handover controllers that allow end-users to specify timing parameters for the robot reach motion, and that provide feedback if the robot cannot satisfy those constraints. End-user tuning with feedback is a useful controller feature in settings where robots have to be re-programmed for varying task requirements but end-users do not have programming knowledge. The two controllers we propose are both receding-horizon controllers that differ in their objective function, and their user specified parameters, and subsequently their user-interface: One controller uses a minimum cumulative jerk (MCJ) objective function, and the other a minimum cumulative error (MCE) objective function. We implemented the controllers on a collaborative robot and conducted two controlled experiments to compare the user experience and performance of these controllers vis-à-vis a baseline proportional velocity (PV) controller. In each experiment, participants (n = 30) interactively tuned the controller parameters, and collaborated with a robot to perform a time-constrained repetitive task. We found that the timing controller with the MCE implementation can provide a better user experience, both while setting the parameters (p =0.011) and performing the handovers with the robot (p < 0.001), and fewer failures (p =0.016) compared to the PV controller, however the MCJ implementation did not provide better user experience compared to the PV controller. The MCJ controller also resulted in more failures than the PV controller. These results could inform the design of usable and effective end-user configurable controllers for human-robot interaction.

We propose a novel planning technique for satisfying tasks specified in temporal logic in partially revealed environments. We define high-level actions derived from the environment and the given task itself, and estimate how each action contributes to progress towards completing the task. As the map is revealed, we estimate the cost and probability of success of each action from images and an encoding of that action using a trained neural network. These estimates guide search for the minimum-expected-cost plan within our model. Our learned model is structured to generalize across environments and task specifications without requiring retraining. We demonstrate an improvement in total cost in both simulated and real-world experiments compared to a heuristic-driven baseline.

Robots deployed in airports, malls, and stadiums today require expert oversight, pre-provided maps, and infrastructure. These systems are engineered to their specific deployment spaces and rely heavily on geometric maps for motion planning. In this work we consider a robot with only local-sensing and present a navigation strategy that uses signs and homotopy classes to fuel planning. We prove that in the worst-case, this strategy still maintains the probabilistic completeness that sampling based motion planners provide. Furthermore, we experimentally show that this exploration strategy results in 100% goal completion in real airport floor plans, and demonstrate how the robot’s sensing capabilities affects efficiency. We also show the effect of the environment variables, such as total number of obstacles, and density of obstacles, on navigation.

JESSIE is a robotic system that enables novice programmers to program social robots by expressing high-level specifications. We employ control synthesis with a tangible front-end to allow users to define complex behavior for which we automatically generate control code. We demonstrate JESSIE in the context of enabling clinicians to create personalized treatments for people with mild cognitive impairment (MCI) on a Kuri robot, in little time and without error. We evaluated JESSIE with neuropsychologists who reported high usability and learnability. They gave suggestions for improvement, including increased support for personalization, multi-party programming, collaborative goal setting, and re-tasking robot role post-deployment, which each raise technical and sociotechnical issues in HRI. We exhibit JESSIE's reproducibility by replicating a clinician-created program on a TurtleBot~2. As an open-source means of accessing control synthesis, JESSIE supports reproducibility, scalability, and accessibility of personalized robots for HRI.

Recently, Linear Temporal Logic (LTL) has been used as a formalism for defining high-level robot tasks, and LTL synthesis has been used to automatically create correct-by-construction robot control. The underlying premise of this approach is that the robot has a set of actions, or skills, that can be composed to achieve the high- level task. In this paper we consider LTL specifications that cannot be synthesized into robot control due to lack of appropriate skills; we present algorithms for automatically suggesting new or modified skills for the robot that will guarantee the task will be achieved. We demonstrate our approach with a physical Baxter robot and a simulated KUKA IIWA arm.

In this paper, we propose an abstraction that captures high-level formation and location-based swarm behaviors, and an automated control synthesis framework to generate correct-by-construction behaviors. Our abstraction includes symbols representing both possible formations and physical locations in the workspace. We allow users to write linear temporal logic (LTL) specifications over the symbols to specify high-level tasks for the swarm. To satisfy a specification, we automatically synthesize a centralized symbolic plan, and environment and swarm-size-dependent motion controllers that are guaranteed to implement the symbolic transitions. In addition, using integer programming (IP), we assign robots to different sub-swarms to execute the synthesized symbolic plan. Our framework gives insights into controlling a large fleet of autonomous robots to achieve complex tasks which require composition of behaviors at different locations and coordination among different groups of robots in a correct-by-construction way. We demonstrate the proposed framework in simulation with 16 UAVs and 8 ground vehicles, and on a physical platform with 20 ground robots, showcasing the generality of the approach and discussing the implications of controlling constrained physical hardware.

The great promise of modular robots is the ability to create on demand robots; however, choosing the “right” design based on a task is still a challenging problem. In this paper, we present an approach to automatically synthesize both the design and control for modular robots from a task description. In particular, we focus on manipulators composed of one degree-of-freedom (DoF) modules. Our approach is able to handle partially infeasible tasks by either identifying the infeasible part and finding a design that satisfies the feasible part or searching for multiple designs that together satisfy the entire task. We compare our approach to a baseline genetic algorithm in a series of increasingly complex environments.

This paper combines techniques from Formal Methods and Human-Robot Interaction (HRI) to address the challenge of a robot walking with a human while maintaining a socially acceptable distance and avoiding collisions. We formulate a set of constraints on the robot motion using Satisfiability Modulo Theories (SMT) formulas, and synthesize robot control that is guaranteed to be safe and correct. Due to its use of high-level formal specifications, the controller is able to provide feedback to the user in situations where human behavior causes the robot to fail. This feedback allows the human to adjust their behavior and recover joint navigation. We demonstrate the behavior of the robot in a variety of simulated scenarios and compare it to utility-based side-by-side navigation control.

Soft robots utilize compliant materials to perform motions and behaviors not typically achievable by rigid bodied systems. These materials and soft actuator fabrication methods have been leveraged to create multigait walking soft robots. However, soft materials are prone to failure, restricting the ability of soft robots to accomplish tasks. In this work we address the problem of generating reactive controllers for multigait walking soft robots that are resilient to actuator failure by applying methods of formal synthesis. We present a sensing-based abstraction for actuator performance, provide a framework for encoding multigait behavior and actuator failure in Linear Temporal Logic (LTL), and demonstrate synthesized controllers on a physical soft robot.

We present a controller for human-robot handovers that is automatically synthesized from high-level specifications in Signal Temporal Logic (STL). In contrast to existing controllers, this approach can provide formal guarantees on the timing of each of the handover phases. Using synthesis also allows end-users to specify and dynamically change the robot's behaviors using high-level requirements of goals and constraints rather than by tuning low-level controller parameters. We illustrate the proposed approach by replicating the behavior of existing handover strategies from the literature. We also identify specification parameters that are likely to lead to successful handovers using a public database of human-human handovers.

We present a system enabling a modular robot to autonomously build structures in order to accomplish high-level tasks. Building structures allows the robot to surmount large obstacles, expanding the set of tasks it can perform. This addresses a common weakness of modular robot systems, which often struggle to traverse large obstacles. This paper presents the hardware, perception, and planning tools that comprise our system. An environment characterization algorithm identifies features in the environment that can be augmented to create a path between two disconnected regions of the environment. Specially-designed building blocks enable the robot to create structures that can augment the environment to make obstacles traversable. A high-level planner reasons about the task, robot locomotion capabilities, and environment to decide if and where to augment the environment in order to perform the desired task. We validate our system in hardware experiments.

Whether robot controllers are manually designed or synthesized from high-level task specifications, assumptions about the environment need to be made, which can involve adversarial events or cooperative robots. In either case, if these assumptions are violated at runtime, the robot will fail to fulfill its task and will likely do something unexpected. In this paper, we focus on controllers synthesized from linear temporal logic. We tackle the problem of making these controllers robust against environment assumption violations that are common in robot execution. Our solution is a three-layer system: first, we propose an offline approach that accounts for transient violations such that the robot can still complete its task after temporary anomalies; the second layer is an online approach that automatically relaxes the environment assumptions to better capture environment behaviors and that allows the robot to react accordingly; and, finally, we automatically modify the actual environment behaviors, when possible, through negotiation with one of the environment robots operating in the workspace, such that our assumptions are met by the other robot and both robots accomplish their tasks.

The advantage of modular robot systems lies in their flexibility, but this advantage can only be realized if there exists some reliable, effective way of generating configurations (shapes) and behaviors (controlling programs) appropriate for a given task. In this paper, we present an end-to-end system for addressing tasks with modular robots, and demonstrate that it is capable of accomplishing challenging multi-part tasks in hardware experiments. The system consists of four tightly integrated components: (1) A high-level mission planner, (2) A design library spanning a wide set of functionality, (3) A design and simulation tool for populating the library with new configurations and behaviors, and (4) Modular robot hardware. This paper condenses the material originally presented in Jing et al. 2016 into a shorter format suitable for a broad audience.

Today, there are many examples of humans and robots regularly interacting in a variety of domains, such as manufacturing, coordinated assembly, and rehabilitation. A resulting demand for more generally accessible communication interfaces has motivated several recent independent research efforts focused on providing robotic systems with a robust natural language interface. Natural language interfaces enable intuitive interaction for untrained and non-expert users. However, achieving real-time performance is particularly challenging, yet essential, to enable flexible, efficient communication. The length of the language input directly impacts the run-time performance and quickly becomes a practical issue when the input is a sequence of multiple sentences, or a monologue. In this work, we propose a variant of a contemporary probabilistic graphical model for language understanding that introduces novel segmentation of the input into a sequence of sentences to be labeled in order. We introduce the notion of a continuously updated prior context that retains the meaning of previous sentences as the inference process proceeds. This prior context serves as evidence during future sentence evaluations. We evaluate our model on two natural language corpora, and demonstrate its utility on a Clearpath Husky A200 mobile manipulator and a simulated Rethink Robotics Baxter Robot.

Motivated by the provably-correct execution of complex reactive tasks for robots with nonlinear, under-actuated dynamics, our focus is on the synthesis of a library of low-level controllers that implements the behaviors of a high-level controller. The synthesized controllers should allow the robot to react to its environment whenever dynamically feasible given the geometry of the workspace. For any behaviors that cannot guarantee the task given the dynamics, such behaviors should be transformed into dynamically-informative revisions to the high-level task. We therefore propose a framework for synthesizing such low-level controllers and, moreover, offer an approach for re-partitioning and abstracting the system based on the synthesized controller library. We accomplish these goals by introducing a synthesis approach that we call conforming funnels, in which controllers are synthesized with respect to the given high-level behaviors, the geometrical constraints of the workspace, and a robot dynamics model. Our approach computes controllers using a verification approach that optimizes over a wide range of possible controllers to guarantee the geometrical constraints are satisfied. We also devise an algorithm that uses the controllers to re-partition the workspace and automatically adapt the high-level specification with a new discrete abstraction generated on these new partitions. We demonstrate the controllers generated by our synthesis framework in an experimental setting with a KUKA youBot executing a box transportation task.

In this work, we take a step towards bridging the gap between the theory of formal synthesis and its application to real-world, complex, robotic systems. In particular, we present an end-to-end approach for the automatic generation of code that implements high-level robot behaviors in a verifiably correct manner, including reaction to the possible failures of low-level actions. We start with a description of the system defined a priori. Thus, a non-expert user need only specify a high-level task. We automatically construct a formal specification, in a fragment of Linear Temporal Logic (LTL), that encodes the system's capabilities and constraints, the task, and the desired reaction to low-level failures. We then synthesize a reactive mission plan that is guaranteed to satisfy the formal specification, i.e., achieve the task's goals or correctly react to failures. Lastly, we automatically generate a state machine that instantiates the synthesized symbolic plan in software. We showcase our approach using Team ViGIR's software and Atlas humanoid robot and present lab experiments, thus demonstrating the application of formal synthesis techniques to complex robotic systems. The proposed approach has been implemented and open-sourced as a collection of Robot Operating System (ROS) packages, which are adaptable to other systems.

Current methods of grounding natural language instructions do not include reactive or temporal components, making these methods unsuitable for instructions describing tasks as sets of conditional instructions. We introduce the Verifiable Distributed Correspondence Graph (V-DCG) model, which enables the validation of natural language instructions by using Linear Temporal Logic (LTL) specifications together with physical world groundings. We demonstrate the V-DCG model on a physical robot and provide examples of the output our system produces for natural language instructions.

We consider multiple robots operating in a shared workspace, each given a high-level task specification in the form of Linear Temporal Logic (LTL) formulas. The robots have no a priori knowledge about the tasks of the other robots and might run into conflicts during task execution. In this work, we develop algorithms that allow the robots to autonomously resolve conflicts and complete their tasks with correctness guarantees, when possible. In our approach, the robots autonomously detect conflicts and trigger coordination within the subgroup of robots in conflict. The need-based coordination initiates the execution of a global robot controller on each robot in the subgroup until the robots all reach their current goals. The subgroup of robots then return to their local controllers and continue their execution. Our approach captures both the advantage of decentralized robot control and that of centralized robot control. The transition between centralized and decentralized robot control is seamless with guarantees provided.

This paper introduces a motion-planning framework for a hybrid system with general continuous dynamics to satisfy a temporal logic specification consisting of cosafety and safety components in a partially unknown environment. The framework employs a multilayered synergistic planner to generate trajectories that satisfy the specification and adopt an iterative replanning strategy to deal with unknown obstacles. When the discovery of an obstacle renders the specification unsatisfiable, a division between the constraints in the specification is considered. The cosafety component of the specification is treated as a soft constraint, whose partial satisfaction is allowed, while the safety component is viewed as a hard constraint, whose violation is forbidden. To partially satisfy the cosafety component, inspirations are taken from indoor-robotic scenarios, and three types of (unexpressed) restrictions on the ordering of subtasks in the specification are considered. For each type, a partial satisfaction method is introduced, which guarantees the generation of trajectories that do not violate the safety constraints while attending to partially satisfying the cosafety requirements with respect to the chosen restriction type. The efficacy of the framework is illustrated through case studies on a hybrid car-like robot in an office environment.

We present a new framework for reactive synthesis that considers the dynamics of the robot when synthesizing correct-by-construction controllers for nonlinear systems. Many high-level synthesis approaches employ discrete abstractions to reason about the dynamics of the continuous system in a simplified manner. Often, these abstractions are expensive to compute. We circumvent the need to have detailed abstractions for nonlinear systems by proposing a framework for adapting abstractions based on partial solutions to the low-level controller synthesis problem. The contribution of this paper is a reactive synthesis algorithm that makes use of our adaptation procedure to update the high-level strategy each time the non-deterministic discrete abstraction is modified. We combine this with a verified low-level controller synthesis scheme capable of automatically synthesizing controllers for a wide class of nonlinear systems. This novel synthesis framework is demonstrated on a dynamical robot executing an autonomous inspection task.

We consider two robots operating in a common workspace where each can sense the location of the other. Each robot has its own high-level task, given as a temporal logic formula, which may include requirements regarding the other robot (e.g. the robot cannot enter a room that the other robot is currently in). This task is not initially shared with the other robot; therefore, the robots when operating, may find themselves in a conflict situation. In this paper, we develop algorithms that allow the robots to automatically, and in a provably correct manner, resolve the conflict, if possible. If the automated process fails, meaning that the robots cannot both perform their tasks in the same workspace, feedback is provided to a human, that would resolve the conflict (e.g. by changing the robot's tasks). The algorithm is demonstrated with simulated and physical robots in the lab.

The use of formal methods for synthesis has recently enabled the automated construction of verifiable high-level robot control. Most approaches use a discrete abstraction of the underlying continuous domain, and make assumptions about the physical execution of actions given a discrete implementation; examples include when actions will complete relative to each other, and possible changes in the robot's environment while it is performing various actions. Relaxing these assumptions give rise to a number of challenges during the continuous implementation of automatically synthesized hybrid controllers. This paper presents several distinct timing semantics for controller synthesis, and compares them with respect to the assumptions they make on the execution of actions. It includes a discussion of when each set of assumptions is reasonable, and the computational tradeoffs inherent in relaxing them at synthesis time.

Recent advances have enabled the automatic generation of correct-by-construction robot controllers from high-level mission specifications. However, most current approaches operate under the closed-world assumption, i.e., only elements of the world explicitly modeled a priori can be taken into account during execution. In this paper, we tackle the problem of specifying and automatically updating the missions of robots operating in worlds that are open with respect to new elements, such as new objects and regions of interest. We demonstrate our approach in a scenario featuring a robotic courier whose world is open with respect to letters addressed to new recipients.

This paper addresses the problem of designing control schemes for teams of robots engaged in complex highlevel tasks. It presents a method for automatically creating hybrid controllers that ensure that a team of possibly heterogeneous robots satisfies a user-defined high-level task. The proposed approach relaxes constraints on the simultaneous and interleaved motion of the robots, while maintaining constraints on their relative location to guarantee collision-avoidance and prevent deadlock. The approach is demonstrated in the context of a team of robots engaged in sorting objects for recycling.

This paper considers the problem of motion planning for a hybrid robotic system with complex and nonlinear dynamics in a partially unknown environment given a temporal logic specification. We employ a multi-layered synergistic framework that can deal with general robot dynamics and combine it with an iterative planning strategy. Our work allows us to deal with the unknown environmental restrictions only when they are discovered and without the need to repeat the computation that is related to the temporal logic specification. In addition, we define a metric for satisfaction of a specification. We use this metric to plan a trajectory that satisfies the specification as closely as possible in cases in which the discovered constraint in the environment renders the specification unsatisfiable. We demonstrate the efficacy of our framework on a simulation of a hybrid second-order car-like robot moving in an office environment with unknown obstacles. The results show that our framework is successful in generating a trajectory whose satisfaction measure of the specification is optimal. They also show that, when new obstacles are discovered, the reinitialization of our framework is computationally inexpensive.

Recently, formal methods have been used to transform high-level robot tasks into correct-by-construction controllers. While correctness is guaranteed, these inherently discrete methods often lead to behaviors that are not optimal in the continuous sense, i.e. they induce robot paths that are significantly suboptimal. This paper proposes an algorithm for dynamically reordering the robot goals and connecting them via the shortest path with respect to a given continuous metric. The generated robot trajectories are close-to-optimal while satisfying the task specification in a dynamic environment. This method is implemented and simulation results are shown.

Formal methods have recently been successfully applied to construct verifiable high-level robot control. Most approaches use a discrete abstraction of the underlying continuous domain, and make simplifying assumptions about the physical execution of actions given a discrete implementation. Relaxing these assumptions unearths a number of challenges in the continuous implementation of automatically-synthesized hybrid controllers. This paper describes a controller-synthesis framework that ensures correct continuous behaviors by explicitly modeling the activation and completion of continuous low-level controllers. The synthesized controllers exhibit desired properties like immediate reactiveness to sensor events and guaranteed safety of physical executions. The approach extends to any number of robot actions with arbitrary relative timings.

Applying correct-by-construction planning techniques to robots with complex nonlinear dynamics requires new formal analysis methods which guarantee that the requested behaviors can be achieved in the continuous space. In this paper, we construct low-level controllers that ensure the execution of a high-level mission plan. Controllers are generated using trajectory-based verification to produce a set of robust reach tubes which strictly guarantee that the required motions achieve the desired task specification. Reach tubes, computed here by solving a series of sum-of-squares optimization problems, are composed in such a way that all trajectories ensure correct highlevel behaviors. We illustrate the new method using an input-limited unicycle robot satisfying task specifications expressed in linear temporal logic.

A recent method to obtain correct robot controllers is to automatically synthesize them from high-level robot missions that are specified in temporal logic. In this context, we aim for controllers that are optimal, i.e., do not let the robot take unnecessarily costly paths to reach its goals. Previous work on obtaining optimal synthesized robot controllers either ignored interactions with the environment, or assumed a cooperative environment. In this paper, we solve the problem of obtaining optimal robot controllers for adversarial environments. Our main observation is that the quality of a path to a goal has two dimensions: (1) the number of phases in which the robot waits for the environment to perform some actions and (2) the cost of the robot's actions to reach the goal. Our synthesis algorithm can take any prioritization over the possible cost combinations into account, and computes the optimal strategy in a symbolic manner, despite the fact that the action costs can be non-integer. We show the scalability of the new algorithm by example of a delivery problem.

One increasingly popular approach for creating robot controllers for complex tasks is to automatically synthesize a hybrid controller from a high-level task specification. Such an approach, in addition to reducing the time and expertise required for creating a controller, guarantees that the robot will satisfy all of the underlying specifications, given perfect sensing and actuation. This paper investigates the probabilistic guarantees that can be made about the behavior of the robot when the actuation of the robot is no longer assumed to be perfect, as well as the possible specification revisions that can be made to improve the behavior of the robot. The approach described in this paper composes probabilistic models of the environment behavior and the robot actuation error with the synthesized controller, and uses probabilistic model checking techniques to find the probability that the robot satisfies a set of high level specifications. This paper also presents a preliminary approach for analyzing the composed model and automatically generating revisions to improve the robot's high-level behavior.

High-level robot control has recently seen the application of formal methods to the automatic synthesis of correct-by-construction controllers from user-defined specifications. When a specification fails to yield a corresponding controller, existing techniques provide feedback on portions of the specification that cause the failure, but at a coarse granularity. This work provides techniques for extracting minimal explanations of such failures. The approach is shown to provide refinement of the feedback on several example specifications.

This paper illustrates the Linear Temporal Logic MissiOn Planning (LTLMoP) toolkit. LTLMoP is an open source software package that transforms high-level specifications for robot behavior, captured using a structured English grammar, into a robot controller that guarantees the robot will complete its task, if the task is feasible. If the task cannot be guaranteed, LTLMoP provides feedback to the user as to what the problem is. Due to its modular nature, users can control a variety of different robots using LTLMoP, both simulated and physical, with the same specification. It shows an example robot waiter scenario, with LTLMoP controlling both a PR2 in simulation (using Gazebo), showcasing the interface between LTLMoP and the Robot Operating System (ROS)2, as well as an Aldebaran Nao humanoid in the lab.

A key challenge in robotics is the generation of controllers for autonomous, high-level robot behaviors comprising nontrivial sequences of actions, including reactive and repeated tasks. When constructing controllers to fulfill such tasks, it is often not known a priori whether the intended behavior is even feasible; plans are modified on the fly to deal with failures that occur during execution, often still without guaranteeing correct behavior. Recently, formal methods have emerged as a powerful tool to automatically generate autonomous robot controllers that guarantee desired behaviors expressed by a class of temporal logic specifications. However, when the specification cannot be fulfilled, these approaches do not provide the user with a source of failure, making the troubleshooting of specifications an unstructured and time-consuming process. This paper describes an algorithm to automatically analyze an unsynthesizable specification in order to identify causes of failure. It also introduces an interactive game to explore possible causes of unsynthesizability, in which the user attempts to fulfill the robot specification against an adversarial environment. The proposed algorithm and game are implemented as features within the LTLMoP toolkit for robot mission planning.

This video shows a demonstration of a fully autonomous robot, an iRobot ATRV-JR, which can be given commands using natural language. Users type commands to the robot on a tablet computer, which are then parsed and processed using semantic analysis. This information is used to build a plan representing the high level autonomous behaviors the robot should perform [2][1]. The robot can be given commands to be executed immediately (e.g., "Search the floor for hostages.") as well as standing orders for use over the entire run (e.g., "Let me know if you see any bombs.").

The Linear Temporal Logic MissiOn Planning (LTLMoP) toolkit is a software package designed to generate a controller that guarantees a robot satisfies a task specification written by the user in structured English. The controller can be implemented on either a simulated or physical robot. This video illustrates the use of LTLMoP to generate a correct-by-construction robot controller. Here, an Aldebaran Nao humanoid robot carries out tasks as a worker in a simplified grocery store scenario.

This paper uniquely embeds high-level robot controllers with sensor data obtained from abstracting probabilistic anticipation of the behavior of dynamic obstacles. An example problem of an autonomous vehicle operating in an urban environment, in the presence of other vehicles and pedestrians, is used as motivation. The correct-by-construction controller is automatically synthesized from a set of high-level tasks, specified as temporal logic formulas. The anticipated behavior of other vehicles is abstracted to a set of propositions describing the safety of road segments at intersections, and used as the output of high-level sensors for the controller. Such an input to the controller is inherently probabilistic, and this paper investigates the types of probabilistic guarantees that can be made about the system using both formal and statistical analysis.

One of the main challenges in robotics is the generation of controllers for autonomous, high-level robot behaviors comprising a non-trivial sequence of actions. Recently, formal methods have emerged as a powerful tool for automatically generating autonomous robot controllers that guarantee desired behaviors expressed by a class of temporal logic specifications. However, when there is no controller that fulfills the specification, these approaches do not provide the user with a source of failure, making the troubleshooting of specifications an unstructured and time-consuming process. In this paper, we describe a procedure for analyzing an unsynthesizable specification to identify causes of failure. We also provide an interactive game for exploring possible causes of failure, in which the user attempts to fulfill the robot specification against an adversarial environment. Our approach is implemented within the LTLMoP toolkit for robot mission planning.

This paper addresses the challenge of creating correct-by-construction controllers for robots whose actions are of varying execution durations. Recently, Linear Temporal Logic synthesis has been used to construct robot controllers for performing high-level tasks. During continuous execution of these controllers by a physical robot, one or more low-level controllers are invoked simultaneously. If these low-level behaviors take different lengths of time to complete, the system will pass through several potentially unsafe intermediate states. This paper presents an algorithm that either generates a hybrid controller such that every continuous behavior of the robot is safe, or determines at synthesis time that the behavior may be unsafe. The proposed approach is implemented within the LTLMoP toolkit for reactive mission planning.

This paper addresses the challenge of incorporating event memory into the automatic synthesis of hybrid controllers for high-level reactive robot behavior. The goal is to provide a natural, concise grammar for specifying high-level tasks that require remembering past events, and to ensure that the required memory is correctly updated during controller execution. To this end, a structured English grammar for specifying high level behavior is provided that automatically performs memory operations, without requiring explicit definition from the specification designer. This grammar admits intuitive, unambiguous specifications for tasks that implicitly use memory for purposes including non-repeated goals, strictly ordered action sequences, etc. The proposed framework also guarantees the correctness of memory operations during continuous execution. The approach is implemented within the LTLMoP toolkit for reactive mission planning.

This paper discusses the creation of provably correct control for modular robots from high-level tasks expressed using sentences in structured English. Due to the nature of modular robots, we address problems that include requirements on the geometry and motion characteristics of the robot; these requirements are captured using traits in the specification that are then used in the control generation process. Outlined in this paper is our approach for generating all the lower levels of control for a modular robot given the high-level problem statement. The approach includes the use of a configuration-gait-trait library for characterizing modular robots and tools for populating this library such as a physics-based simulator and gait creator. The approach is demonstrated in simulation and with the CKBot hardware platform.

This paper describes the synthesis of correct robot control from high-level tasks that include non-projective locative prepositions. Here, locative prepositions such as `near' and `between' are used to refer to regions in the robot's workspace and are part of a high-level task description such as “Always stay near room 1” or “Visit the area between room 2 and room 3”. These prepositions induce a discrete abstraction of the workspace which, together with the rest of the task, is used to synthesize a correct-by-construction robot controller such that the robot is guaranteed to behave as expected, if the task is feasible. This work presents an important step towards allowing linguistic control of robots that is both intuitive and provably correct.

The Linear Temporal Logic MissiOn Planning (LTLMoP) toolkit is a software package designed to assist in the rapid development, implementation, and testing of high-level robot controllers. In this toolkit, structured English and Linear Temporal Logic are used to write high-level reactive task specifications, which are then automatically transformed into correct robot controllers that can be used to drive either a simulated or a real robot. LTLMoP's modular design makes it ideal for research in areas such as controller synthesis, semantic parsing, motion planning, and human-robot interaction.

This paper provides a frameworkto automaticallygenerate a hybrid controller thatguaranteesthat the robot can achieve its task when a robot model, a class of admissible environments, and a high-level task or behavior for the robot are provided. The desired task specifications, which are expressed in a fragment of linear temporal logic (LTL), can capture complex robot behaviors such as search and rescue, coverage, and collision avoidance. In addition, our framework explicitly captures sensor specifications that depend on the environment with which the robot is interacting, which results in a novel paradigm for sensor-based temporal-logic-motion planning. As one robot is part of the environment of another robot, our sensor-based framework very naturally captures multirobot specifications in a decentralized manner. Our computational approach is based on first creating discrete controllers satisfying specific LTL formulas. If feasible, the discrete controller is then used to guide the sensor-based composition of continuous controllers, which results in a hybrid controller satisfying the high-level specification but only if the environment is admissible.

Given a robot model and a class of admissible environments, this paper provides a framework for automatically and verifiably composing controllers that satisfy high level task specifications expressed in suitable temporal logics. The desired task specifications can express complex robot behaviors such as search and rescue, coverage, and collision avoidance. In addition, our framework explicitly captures sensor specifications that depend on the environment with which the robot is interacting, resulting in a novel paradigm for sensor-based temporal logic motion planning. As one robot is part of the environment of another robot, our sensor-based framework very naturally captures multi-robot specifications. Our computational approach is based on first creating discrete controllers satisfying so-called general reactivity formulas. If feasible, the discrete controller is then used in order to guide the sensor-based composition of continuous controllers resulting in a hybrid controller satisfying the high level specification, but only if the environment is admissible.

What would it be like if we could give our robot high level commands and it would automatically execute them in a verifiably correct fashion in dynamically changing environments? This work demonstrates a method for generating continuous feedback control inputs that satisfy high-level specifications. Using a collection of continuous local feedback control policies in concert with a synthesized discrete automaton, this paper demonstrates the approach on an Ackermann-steered vehicle that satisfies the command "drive around until you find an empty parking space, then park." The system reacts to changing environmental conditions using only local information, while guaranteeing the correct high level behavior. The local policies consider the vehicle body shape as well as bounds on drive and steering velocities. The discrete automaton that invokes the local policies guarantees executions that satisfy the high-level specification based only on information about the current availability of the nearest parking space. This paper also demonstrates coordination of two vehicles using the approach.

Recently, Linear Temporal Logic (LTL) has been successfully applied to high-level task and motion planning problems for mobile robots. One of the main attributes of LTL is its close relationship with fragments of natural language. In this paper, we take the first steps toward building a natural language interface for LTL planning methods with mobile robots as the application domain. For this purpose, we built a structured English language which maps directly to a fragment of LTL.

In this paper, we consider the problem of robot motion planning in order to satisfy formulas expressible in temporal logics. Temporal logics naturally express traditional robot specifications such as reaching a goal or avoiding an obstacle, but also more sophisticated specifications such as sequencing, coverage, or temporal ordering of different tasks. In order to provide computational solutions to this problem, we first construct discrete abstractions of robot motion based on some environmental decomposition. We then generate discrete plans satisfying the temporal logic formula using powerful model checking tools, and finally translate the discrete plans to continuous trajectories using hybrid control. Critical to our approach is providing formal guarantees ensuring that if the discrete plan satisfies the temporal logic formula, then the continuous motion also satisfies the exact same formula.