This paper proposes an optimization-based task and motion planning framework, named “Logic Network Flow”, to integrate signal temporal logic (STL) specifications into efficient mixed-binary linear programmings. In this framework, temporal predicates are encoded as polyhedron constraints on each edge of the network flow, instead of as constraints between the nodes as in the traditional Logic Tree formulation. Synthesized with Dynamic Network Flows, Logic Network Flows render a tighter convex relaxation compared to Logic Trees derived from these STL specifications. Our formulation is evaluated on several multi-robot motion planning case studies. Empirical results demonstrate that our formulation outperforms Logic Tree formulation in terms of computation time for several planning problems. As the problem size scales up, our method still discovers better lower and upper bounds by exploring fewer number of nodes during the branch-and-bound process, although this comes at the cost of increased computational load for each node when exploring branches.

Humanoid robots offer significant advantages for search and rescue tasks, thanks to their capability to traverse rough terrains and perform transportation tasks. In this study, we present a task and motion planning framework for search and rescue operations using a heterogeneous robot team composed of humanoids and aerial robots. We propose a terrain-aware Model Predictive Controller (MPC) that incorporates terrain elevation gradients learned using Gaussian processes (GP). This terrain-aware MPC generates safe navigation paths for the bipedal robots to traverse rough terrain while minimizing terrain slopes, and it directs the quadrotors to perform aerial search and mapping tasks. The rescue subjects' locations are estimated by a target belief GP, which is updated online during the map exploration. A high-level planner for task allocation is designed by encoding the navigation tasks using syntactically cosafe Linear Temporal Logic (scLTL), and a consensus-based algorithm is designed for task assignment of individual robots. We evaluate the efficacy of our planning framework in simulation in an uncertain environment with various terrains and random rescue subject placements.

We consider the problem of tracking a reference trajectory for dynamical systems subject to a priori unknown state-dependent disturbance behavior. We propose a formulation that embeds the uncertain system into a higher dimensional deterministic system that accounts for worst case disturbances. Our main insight is that a single controlled trajectory of this embedding system corresponds to a controlled forward invariant interval tube around the reference trajectory. By taking observations of the system, we then propose to estimate the state-dependent uncertainty with Gaussian Process regression, which improves the accuracy of the forward invariant tube as data is collected. Given a safety objective, we also provide conditions on when an additional observation of the unknown disturbance behavior needs to be collected to maintain safety. We demonstrate our formulation on a case study of a planar multirotor attempting a safe landing in an unknown wind field.

In this work we develop a software-in-the-loop simulator platform for Crazyflie nano quadrotor drone fleets. One of the challenges in maintaining a large fleet of drones is ensuring that the fleet performs its task as expected without collision, and this becomes more challenging as the number of drones scales, possibly into the hundreds. Software-in-the-loop simulation is an important component in verifying that drone fleets operate correctly and can significantly reduce development time. The simulator interface that we develop runs an instance of the Crazyflie flight stack firmware for each individual drone on a commercial, desktop machine along with a sensors and communication plugin on Gazebo Sim. The plugin transmits simulated sensor information to the firmware along with a socket link interface to run external scripts that would be run on a ground station during hardware deployment. The plugin simulates a radio communication delay between the drones and the ground station to test offboard control algorithms and high-level fleet commands. To validate the proposed simulator, we provide a case study of decentralized model predictive control (MPC) that is run on a ground station to command a fleet of sixteen drones to follow a specified trajectory. We first run the controller on the simulator interface to verify performance and robustness of the algorithm before deployment to a Crazyflie hardware experiment in the Georgia Tech Robotarium.

We study the problem of bipedal robot navigation in complex environments with uncertain and rough terrain. In particular, we consider a scenario in which the robot is expected to reach a desired goal location by traversing an environment with uncertain terrain elevation. Such terrain uncertainties induce not only untraversable regions but also robot motion perturbations. Thus, the problems of terrain mapping and locomotion stability are intertwined. We evaluate three different kernels for Gaussian process (GP) regression to learn the terrain elevation. We also learn the motion deviation resulting from both the terrain as well as the discrepancy between the reduced-order Prismatic Inverted Pendulum Model used for planning and the full-order locomotion dynamics. We propose a hierarchical locomotion-dynamics-aware sampling-based navigation planner. The global navigation planner plans a series of local waypoints to reach the desired goal locations while respecting locomotion stability constraints. Then, a local navigation planner is used to generate a sequence of dynamically feasible footsteps to reach local waypoints. We develop a novel trajectory evaluation metric to minimize motion deviation and maximize information gain of the terrain elevation map. We evaluate the efficacy of our planning framework on Digit bipedal robot simulation in MuJoCo.i

This paper presents an incremental replanning algorithm, dubbed LTL-D*, for temporal-logic-based task planning in a dynamically changing environment. Unexpected changes in the environment may lead to failures in satisfying a task specification in the form of a Linear Temporal Logic (LTL). In this study, the considered failures are categorized into two classes: (i) the desired LTL specification can be satisfied via replanning, and (ii) the desired LTL specification is infeasible to meet strictly and can only be satisfied in a "relaxed" fashion. To address these failures, the proposed algorithm finds an optimal replanning solution that minimally violates desired task specifications. In particular, our approach leverages the D* Lite algorithm and employs a distance metric within the synthesized automaton to quantify the degree of the task violation and then replan incrementally. This ensures plan optimality and reduces planning time, especially when frequent replanning is required. Our approach is implemented in a robot navigation simulation to demonstrate a significant improvement in the computational efficiency for replanning by two orders of magnitude.

This paper proposes Koopman operator theory and the related algorithm dynamical mode decomposition (DMD) for analysis and control of signalized traffic flow networks. DMD provides a model-free approach for representing complex oscillatory dynamics from measured data, and we study its application to several problems in signalized traffic. We first study a single signalized intersection, and we propose applying this method to infer traffic signal control parameters such as phase timing directly from traffic flow data. Next, we propose using the oscillatory modes of the Koopman operator, approximated with DMD, for early identification of unstable queue growth that has the potential to cause cascading congestion. Then we demonstrate how DMD can be coupled with knowledge of the traffic signal control status to determine traffic signal control parameters that are able to reduce queue lengths. Lastly, we demonstrate that DMD allows for determining the structure and the strength of interactions in a network of signalized intersections. All examples are demonstrated using a case study network instrumented with high resolution traffic flow sensors.

In this work, we show how controlled robustly forward invariant sets for systems with disturbances are efficiently identified via the application of the mixed monotonicity property. A mixed monotone system can be embedded in a related deterministic embedding system with twice as many states but for which the dynamics are monotone; one can then apply the powerful theory of monotone dynamical systems to the embedding system to conclude useful properties of the initial mixed monotone system. Using this technique, we present a method for verifying state-feedback controllers against safety (set invariance) constraints, and our approach involves evaluating a control barrier function type condition that requires the vector field of the embedding system to point into a certain southeast cone. This approach also facilitates the construction of runtime assurance mechanisms for controlled systems with disturbances, and we study system safety in the presence of state uncertainty as well. The results and findings of this work are demonstrated through two numerical examples where we study (i) the verification of a controlled spacecraft system against a safety constraint, and (ii) the formation of a runtime assurance mechanism that functions in the presence of uncertain state measurements.

In this paper we discuss how to use a barrier function that is subject to kinematic constraints and limited sensing in order to guarantee that fixed wing unmanned aerial vehicles (UAVs) will maintain safe distances from each other at all times despite being subject to sensing constraints. Prior work has shown that a barrier function can be used to guarantee safe system operation when the state can be sensed at all times. However, we show that this construction does not guarantee safety when the UAVs are subject to limited range sensing. To resolve this issue, we introduce a method for constructing a new barrier function that accommodates limited sensing range from a previously existing barrier function that may not necessarily accommodate limited range sensing. We show that, under appropriate conditions, the newly constructed barrier function ensures system safety even in the presence of limited range sensing. We demonstrate the contribution of this paper in a simulated scenario of 20 fixed wing aircraft where the vehicles are able to maintain safe distances from each other even though the vehicles are subject to limited range sensing.

A number of coordinated behaviors are proposed for achieving specific tasks for multirobot systems. However, since most applications require more than one such behavior, one needs to be able to compose together sequences of behaviors while respecting local information flow constraints. Specifically, when the interagent communication depends on interrobot distances, these constraints translate into particular configurations that must be reached in finite time in order for the system to be able to transition between the behaviors. To this end, we develop a distributed framework based on finite-time convergence control barrier functions that enables a team of robots to adjust its configuration in order to meet the communication requirements for the different tasks. In order to demonstrate the significance of the proposed framework, we implemented a full-scale scenario where a team of eight planar robots explore an urban environment in order to localize and rescue a subject.

In this article, we propose a framework for the control of mobile robots subject to temporal logic specifications using barrier functions. Complex task specifications can be conveniently encoded using linear temporal logic. In particular, we consider a fragment of linear temporal logic, which encompasses a large class of motion planning specifications for a robotic system. Control barrier functions have recently emerged as a convenient tool to guarantee reachability and safety for a system. In addition, they can be encoded as affine constraints in a quadratic program. In this article, a fully automatic framework that translates a user defined specification in temporal logic to a sequence of barrier function based quadratic programs is presented. In addition, with the aim of alleviating infeasibility scenarios, we propose methods for composition of barrier functions as well as a prioritization-based control method to guarantee feasibility of the controller. We prove that the resulting system trajectory synthesized by the proposed controller satisfies the given specification. Robotic simulation and experimental results are provided in addition to the theoretical framework.

In this paper, we propose a graph-based search method to optimally allocate tasks to a team of robots given a global task specification. In particular, we define these agents as discrete transition systems. In order to allocate tasks to the team of robots, we decompose finite linear temporal logic (LTL) specifications and consider agent specific cost functions. We propose to use the stochastic optimization technique, cross entropy, to optimize over this cost function. The multi-agent task allocation cross-entropy (MTAC-E) algorithm is developed to determine both when it is optimal to switch to a new agent to complete a task and minimize the costs associated with individual agent trajectories. The proposed algorithm is verified in simulation and experimental results are included.

This paper proposes a distributed field mapping algorithm that drives a team of robots to explore and learn an unknown scalar field. The algorithm is based on a bio-inspired approach known as Speeding-Up and Slowing-Down (SUSD) for distributed source seeking problems. Our algorithm leverages a Gaussian Process model to predict field values as robots explore. By comparing Gaussian Process predictions with measurements of the field, agents search along the gradient of the model error while simultaneously improving the Gaussian Process model. We provide a proof of convergence to the gradient direction and demonstrate our approach in simulation and experiments using 2D wheeled robots and 2D flying autonomous miniature blimps.

Control barrier functions are mathematical constructs used to guarantee safety for robotic systems. When integrated as constraints in a quadratic programming optimization problem, instantaneous control synthesis with real-time performance demands can be achieved for robotics applications. Prevailing use has assumed full knowledge of the safety barrier functions, however there are cases where the safe regions must be estimated online from sensor measurements. In these cases, the corresponding barrier function must be synthesized online. This paper describes a learning framework for estimating control barrier functions from sensor data. Doing so affords system operation in unknown state space regions without compromising safety. Here, a support vector machine classifier provides the barrier function specification as determined by sets of safe and unsafe states obtained from sensor measurements. Theoretical safety guarantees are provided. Experimental ROS-based simulation results for an omnidirectional robot equipped with LiDAR demonstrate safe operation.

In this paper, we study the problem of navigating quadcopters through a sequence of hoops. The specification may be given directly or indirectly via a linear temporal logic (LTL) formula. We approach this problem in three phases. First, we introduce a planner that generates a path through a given sequence of hoops. Second, we augment our planner to leverage a given specification in linear temporal logic (LTL) and generate a sequence that satisfies this specification. Third, we implement cross-entropy optimization on this planner to enhance trajectory performance where quadcopter trajectories are modified within the solution space to optimize over a cost function. We implement this planner as a novel interaction modality between users and quadcopters on the Robotarium. Simulation and experimental results are provided.

We present an efficient computational procedure for finite abstraction of discrete-time mixed monotone systems by considering a rectangular partition of the state space. Mixed monotone systems are decomposable into increasing and decreasing components, and significantly generalize the well known class of monotone systems. We tightly overapproximate the one-step reachable set from a box of initial conditions by computing a decomposition function at only two points, regardless of the dimension of the state space. We apply our results to verify the dynamical behavior of a model for insect population dynamics and to synthesize a signaling strategy for a traffic network.