In this article, a new model for 3D motion planning, applicable to aerial vehicles, is proposed to connect an initial and final configuration subject to pitch rate and yaw rate constraints. The motion planning problem for a curvature-constrained vehicle over the surface of a sphere is identified as an intermediary problem to be solved, and it is the focus of this paper. In this article, the optimal path candidates for a vehicle with a minimum turning radius$r$moving over a unit sphere are derived using a phase portrait approach. We show that the optimal path is$CGC$or concatenations of$C$segments through simple proofs, where$C = L, R$denotes a turn of radius$r$and$G$denotes a great circular arc. We generalize the previous result of optimal paths being$CGC$and$CCC$paths for$r \in (0, \frac{1}{2}]\bigcup \lbrace \frac{1}{\sqrt{2}}\rbrace$to$r \leq \frac{\sqrt{3}}{2}$to account for vehicles with a larger$r$. We show that the optimal path is$CGC, CCCC,$for$r \leq \frac{1}{\sqrt{2}},$and$CGC, CC_\pi C, CCCCC$for$r \leq \frac{\sqrt{3}}{2}.$Additionally, we analytically construct all candidate paths and provide the code in a publicly accessible repository.

In this paper, we propose a new modeling approach and a fast algorithm for 3D motion planning, applicable for fixed-wing unmanned aerial vehicles. The goal is to construct the shortest path connecting given initial and final configurations subject to motion constraints. Our work differs from existing literature in two ways. First, we consider full vehicle orientation using a body-attached frame, which includes roll, pitch, and yaw angles. However, existing work uses only pitch and/or heading angle, which is insufficient to uniquely determine orientation. Second, we use two control inputs to represent bounded pitch and yaw rates, reflecting control by two separate actuators. In contrast, most previous methods rely on a single input, such as path curvature, which is insufficient for accurately modeling the vehicle's kinematics in 3D. We use a rotation minimizing frame to describe the vehicle's configuration and its evolution, and construct paths by concatenating optimal Dubins paths on spherical, cylindrical, or planar surfaces. Numerical simulations show our approach generates feasible paths within 10 seconds on average and yields shorter paths than existing methods in most cases.

This article studies the time-optimal path planning problem for a convexified Reeds-Shepp (CRS) vehicle on a unit sphere, capable of both forward and backward motion, with speed bounded in magnitude by 1 and turning rate bounded in magnitude by a given constant. For the case in which the turning-rate bound is at least 1, using Pontryagin's Maximum Principle and a phase-portrait analysis, we show that the optimal path connecting a given initial configuration to a desired terminal configuration consists of at most six segments drawn from three motion primitives: tight turns, great circular arcs, and turn-in-place motions. A complete classification yields a finite sufficient list of 23 optimal path types with closed-form segment angles derived. The complementary case in which the turning-rate bound is less than 1 is addressed via an equivalent reformulation. The proposed formulation is applicable to underactuated satellite attitude control, spherical rolling robots, and mobile robots operating on spherical or gently curved surfaces. The source code for solving the time-optimal path problem and visualization is publicly available at https://github.com/sixuli97/Optimal-Spherical-Convexified-Reeds-Shepp-Paths.

In this paper, we investigate the selection of time headway to ensure robust string stability in connected and autonomous vehicle platoons in the presence of signal noise in Vehicle-to-Vehicle (V2V) communication. In particular, we consider the effect of noise in communicated vehicle acceleration from the predecessor vehicle to the follower vehicle on the selection of the time headway in predecessor-follower type vehicle platooning with a Constant Time Headway Policy (CTHP). Employing a CTHP based control law for each vehicle that utilizes onboard sensors for measurement of position and velocity of the predecessor vehicle and wireless communication network for obtaining the acceleration of the predecessor vehicle, we investigate how the implementable time headway is affected by communicated signal noise. We derive constraints on the CTHP controller gains for predecessor acceleration, velocity error and spacing error and a lower bound on the time headway which will ensure robust string stability of the platoon against signal noise. We perform comparative numerical simulations on an example to illustrate the main results.

In this paper, we provide a systematic procedure for designing cooperative adaptive cruise control (CACC) systems that are robust to parasitic actuation lag in braking and propulsion and delay in the communicated acceleration from the predecessor vehicle. In particular, we derive a tight lower bound on the employable time headway in CACC systems for guaranteeing robust string stability. The lower bound on the time headway is dependent on the upper bound on the parasitic actuation lag (τ0) and the communication delay (ℓ). The main result of the paper is that if τ0exceeds ℓ, then the employable time headway is lower bounded by τ0+ℓ. Otherwise, it is better to use adaptive cruise control (ACC) where the employable time headway is lower bounded by 2τ0. The above results on CACC systems are then extended to next-generation CACC (CACC+) systems that employ information from multiple predecessor vehicles. Several comparative numerical simulations for a representative maneuver corroborate the main results.

Ensuring safety is the most important factor in connected and autonomous vehicles, especially in emergency braking situations. As such, assessing the safety benefits of one information topology over other is a necessary step towards evaluating and ensuring safety. In this paper, we compare the safety benefits of a cooperative adaptive cruise control which utilizes information from one predecessor vehicle (CACC) with the one that utilizes information from multiple predecessors (CACC+) for the maintenance of spacing under an emergency braking scenario. A constant time headway policy is employed for maintenance of spacing (that includes a desired standstill spacing distance and a velocity dependent spacing distance) between the vehicles in the platoon. The considered emergency braking scenario consists of braking of the leader vehicle of the platoon at its maximum deceleration and that of the following vehicles to maintain the spacing as per CACC or CACC+. By focusing on the standstill spacing distance and utilizing Monte Carlo simulations, we assess the safety benefits of CACC+ over CACC by utilizing the following safety metrics: (1) probability of collision, (2) expected number of collisions, and (3) severity of collision (defined as the relative velocity of the two vehicles at impact). We present and provide discussion of these results.

In this article, we consider a multi-agent path planning problem in a partially impeded environment. The impeded environment is represented by a graph with select road segments (edges) in disrepair impeding vehicular movement in the road network. A primary vehicle, which we refer to as a convoy, wishes to travel from a starting location to a destination while minimizing some accumulated cost. The convoy may traverse an impeded edge for an additional cost (associated with repairing the edge) than if it were unimpeded. A support vehicle, which we refer to as a service vehicle, is simultaneously deployed to assist the convoy by repairing edges, reducing the cost for the convoy to traverse those edges. The convoy is permitted to wait at any vertex to allow the service vehicle to complete repairing an edge. The service vehicle is permitted to terminate its path at any vertex. The goal is then to find a pair of paths so the convoy reaches its destination while minimizing the total time (cost) the two vehicles are active, including any time the convoy waits. We refer to this problem as the Assisted Shortest Path Problem (ASPP). We present a generalized permanent labeling algorithm (GPLA) to find an optimal solution for the ASPP. We also introduce additional modifications to the labeling algorithm to significantly improve the computation time and refer to the modified labeling algorithm as GPLA*. Computational results are presented to illustrate the effectiveness of GPLA* in solving the ASPP.Note to Practitioners—One motivation for this work is to improve the efficiency of autonomous warehouse operations, where multiple robots need to coordinate their plans. Take for example two robots operating in a warehouse where one robot is moving goods and the second robot is making repairs or clearing obstructions (fallen goods, objects left by workers, etc.) along the way. The presented algorithm’s underlying structure is relatively simple and the algorithm itself does not require special software or solvers. The algorithm generates sub-optimal solutions as it progresses and terminates with the optimal solution. A large class of problems involving asynchronous actions between two or more agents can be handled using the presented algorithm or an extension of it. In this paper we restrict ourselves to two agents. A limitation of the presented algorithm and its possible extensions is the memory required as the graph representing the problem grows in size. We compare our work against an algorithm with similar approach (centralized$A^*$) and show that the presented algorithm is superior in both memory and computational time. We also present results on relatively large graphs to show the algorithm has practical value. This work can also be applied to rescue missions for people to escape wildfires, flooding or other natural disasters. A robotic agent can scout ahead for impacted pathways and assist victim(s) find the best path to escape to safety.

Persistent monitoring missions require an up-to-date knowledge of the changing state of the underlying environment. Unmannned aerial vehicles (UAVs) can be gainfully employed to continually visit a set of targets representing tasks (and locations) in the environment and collect data therein for long time periods. The enduring nature of these missions requires the UAV to be regularly recharged at a service station. In this article, we consider the case in which the service station is not colocated with any of the targets. An efficient monitoring requires the revisit time, defined as the maximum of the time elapsed between successive revisits to targets, to be minimized. Here, we consider the problem of determining UAV routes that lead to the minimum revisit time. The problem is NP-hard, and its computational difficulty increases with the fuel capacity of the UAV. We develop an algorithm to construct near-optimal solutions to the problem quickly when the fuel capacity exceeds a threshold. We also develop lower bounds to the optimal revisit time and use these bounds to demonstrate (through numerical simulations) that the constructed solutions are, on an average, at most 0.01% away from the optimum.

Recent advances in vehicle connectivity have allowed formation of autonomous vehicle platoons for improved mobility and traffic throughput. In order to avoid a pile-up in such platoons, it is important to ensure platoon (string) stability, which is the focus of this work. As per conventional definition of string stability, the power (2-norm) of the spacing error signals should not amplify downstream in a platoon. But in practice, it is the infinity-norm of the spacing error signal that dictates whether a collision occurs. We address this discrepancy in the first part of our work, where we reconsider string stability from a safety perspective and develop an upper limit on the maximum spacing error in a homogeneous platoon as a function of the acceleration maneuver of the lead vehicle. In the second part of this paper, we extend our previous results by providing the minimum achievable time headway for platoons with two-predecessor lookup schemes experiencing burst-noise packet losses. Finally, we utilize throttle and brake maps to develop a longitudinal vehicle model and validate it against a Lincoln MKZ which is then used for numerical corroboration of the proposed time headway selection algorithms.

In this article, we introduce a cooperative path planning algorithm for a cardinal and a support robot where the cardinal robot is unable to traverse a subset of edges in a network until the support robot has first traversed them. This subset of edges represent paths in an environment that are initially unavailable to the cardinal robot and require the assistance of the support robot. A (2 + α)-approximation algorithm (where α is the supremum of the ratio of the travel time of the support robot versus the travel time of the cardinal robot) is presented for this problem and is applied to various types of networks in order to examine the quality of the solutions it produces. We then conclude by discussing some potential future work concerning variations of this problem.

This article addresses a persistent monitoring problem (PMP) that requires an unmanned aerial vehicle (UAV) to repeatedly visit n targets of equal priority. The UAV has limited onboard fuel/charge and must be regularly serviced at a depot. Given a fixed number of visits, k, for the UAV to the targets between successive services, the objective of the PMP is to determine an optimal sequence of visits such that the maximum time elapsed between successive visits to any target is minimized. This planning problem is a generalization of the traveling salesman problem and is NP-hard. We characterize the optimal solutions to this problem for different values of k and develop algorithms that can compute the optimal solutions relatively fast. Numerical results are also presented to corroborate the performance of the proposed approach.

In this paper, we investigate the benefits of vehicle-to-vehicle (V2V) communication for autonomous vehicles and provide results on how V2V information helps reduce employable time headway in the presence of parasitic lags. For a string of vehicles adopting a constant time headway policy and availing the on-board information of predecessor's vehicle position and velocity, the minimum employable time headway (hmin) must be lower bounded by 2τ0for string stability, where τ0is the maximum parasitic actuation lag. In this paper, we quantify the benefits of using V2V communication in terms of a reduction in the employable time headway: 1) If the position and velocity information of r immediately preceding vehicles is used, then hmin can be reduced to 4τ0/(1 + r); 2) furthermore, if the acceleration of `r' immediately preceding vehicles is used, then hmincan be reduced to 2τ0/(1 + r); and 3) if the position, velocity, and acceleration of the immediate and the r-th predecessors are used, then hmin≥ 2τ0/(1 + r). Note that cases (2) and (3) provide the same lower bound on the minimum employable time headway; however, case (3) requires much less communicated information.

This paper is focused on the development and analysis of suboptimal decision algorithms for a collection of robots that assist a remotely located operator in perimeter surveillance. The operator is tasked with the classification of incursions across the perimeter. whenever there is an incursion into the perimeter, an unattended ground sensor (UGS) in the vicinity, signals an alert. A robot services the alert by visiting the alert location, collecting information, e.g., photo and video imagery, and transmitting it to the operator. The accuracy of operator's classification depends on the volume and freshness of information gathered and provided by the robots at locations where incursions occur. There are two competing objectives for a robot: it needs to spend adequate time at an alert location to collect evidence for aiding the operator in accurate classification but it also needs to service other alerts as soon as possible, so that the evidence collected is relevant. The decision problem is to determine the optimal amount of time a robot must spend servicing an alert. The incursions are stochastic and their statistics are assumed to be known. This problem can be posed as a Markov Decision Problem. However, even for two robots and five UGS locations, the number of states is of the order of billions rendering exact dynamic programming methods intractable. Approximate dynamic programming (ADP) via linear programming (LP) provides a way to approximate the value function and derive suboptimal strategies. The novel feature of this paper is the derivation of a tractable lower bound via LP and the construction of a suboptimal policy whose performance improves upon the lower bound. An illustrative perimeter surveillance example corroborates the results derived in this paper. Note to Practitioners-In practice, one often encounters the curse of dimensionality in the application of dynamic programming to determine optimal policies for controlled Markov chains. This is true, in particular, for dynamic scheduling problems involving multiple robots/servers and queues of tasks that arrive in a stochastic fashion. The computation of value function, critical to the determination of optimal policies, is nearly impractical. Hence, one must settle for suboptimal policies. Two natural questions arise: (1) How does one construct a suboptimal policy? (2) How “good” is the constructed suboptimal policy? A common strategy to tackle the first problem is to approximate the value function and construct a suboptimal policy that is greedy with respect to the approximate value function. Typically, an approximate value function is constructed via a choice of basis functions. The question of how to choose the basis functions systematically for any problem is a difficult one; usually, the structure of the problem at hand is exploited in the construction of basis functions. The same approach is taken here and the state space is partitioned based on the reward structure and the optimal cost-to-go or value function is approximated by a constant over each partition. The second question is related to the first question in the sense that one needs to construct bounds for the performance of a suboptimal policy. In this paper, we construct upper and lower bounds for the value function (optimal performance) and use the lower bound as an approximate value function. Furthermore, we also show that the resulting suboptimal policy comes with a performance guarantee, in that it improves on the lower bound, it was derived from. Literature is replete with techniques for computing upper bounds; however, there is little work on lower bounds, which are also required for bounding the suboptimality of the policy. One encounters prohibitively large number of constraints in the case of computing an upper bound and has to deal with disjunctive linear inequalities in the case of a lower bound. The problem structure is exploited here to circumvent these difficulties. The upper and lower bounds to the value function developed in this paper could also be used to refine the partitions by identifying the partition with the largest difference between the upper and lower bounds; such a partition could be refined further using the structure of the problem. For practitioners, this could be a useful set of tools for generating suboptimal policies for any controlled Markov chain with a reward function that is amenable to state aggregation.

A novel mixed initiative optimal control system for intelligence, surveillance and reconnaissance (ISR) operations which entails human-machine teaming has been developed. The scenario entails a camera-equipped unmanned air vehicle sequentially overflying geolocated objects of interest, which need to be classified as either a true or false target by a human operator. The vehicle is allowed a prespecified number of revisits, such that an object can be looked at, a second time, under better viewing conditions. The overarching goal is to correctly classify the objects and minimize the false alarm (FA) and missed detection (MD) rates. We design a stochastic controller that computes if and when a revisit is necessary and also the optimal revisit state, i.e., viewing altitude and aspect angle. The concept of operation is such that the critical task of detection/pattern recognition is relegated to the human operator, whereas optimal decision making is entrusted to the machine. The stochastic dynamic programming-based decision algorithm is, however, informed about the performance of the human operator via an empirical human perception model. The model is experimentally obtained in the form of state-dependent confusion matrices. The optimal closed-loop ISR system is shown to experimentally achieve a FA rate of 5% and MD rate of 12%, which are significantly lower than the open-loop operator-only performance metrics. The performance improvements that were observed are relevant to a particular operator, and thus, the study suggests that the same improvements could conceivably be achieved with other test subjects.

This paper is about the allocation of tours of m targets to n vehicles. The motion of the vehicles satisfies a nonholonomic constraint (i.e., the yaw rate of the vehicle is bounded). Each target is to be visited by one and only one vehicle. Given a set of targets and the yaw rate constraints on the vehicles, the problem addressed in this paper is 1) to assign each vehicle a sequence of targets to visit, and 2) to find a feasible path for each vehicle that passes through the assigned targets with a requirement that the vehicle returns to its initial position. The heading angle at each target location may not be specified. The objective function is to minimize the sum of the distances traveled by all vehicles. A constant factor approximation algorithm is presented for the above resource allocation problem for both the single and the multiple vehicle case. Note to Practitioners-The motivation for this paper stems from the need to develop resource allocation algorithms for unmanned aerial vehicles (UAVs). Small autonomous UAVs are seen as ideal platforms for many applications, such as searching for targets, mapping a given area, traffic surveillance, fire monitoring, etc. The main advantage of using these small autonomous vehicles is that they can be used in situations where a manned mission is dangerous or not possible. Resource allocation problems naturally arise in these applications where one would want to optimally assign a given set of vehicles to the tasks at hand. The feature that differentiates these resource allocation problems from similar problems previously studied in the literature is that there are constraints on the motion of the vehicle. This paper addresses the constraint that captures the inability of a fixed wing aircraft to turn at any arbitrary yaw rate. The basic problem addressed in this paper is as follows: Given n vehicles and m targets, find a path for each vehicle satisfying yaw rate contraints such that each target is visited exactly once by a vehicle and the total distance traveled by all vehicles is minimized. We assume that the targets are at least 2r apart, where r is the minimum turning radius of the vehicle. This is a reasonable assumption because the sensors on these vehicles can map or see an area whose width is at least 2r. We give an algorithm to solve this problem by combining ideas from the traveling salesman problem and the path planning literature. We also show how these algorithms perform in the worst-case scenario

The safe operation of vehicles on roads depends, among other things, on a properly functioning brake system. Air brake systems are widely used in commercial vehicles such as trucks, tractor-trailers, and buses. In these brake systems, compressed air is used as the energy transmitting medium to actuate the foundation brakes mounted on the axles. In this paper, a model-based diagnostic system for air brakes is presented. This diagnostic system is based on a nonlinear model for predicting the pressure transients in the brake chamber that correlates the brake chamber pressure to the treadle valve (brake application valve) plunger displacement and the pressure of the air supplied to the brake system. Leaks and "out-of-adjustment" of push rods are two prominent defects that affect the performance of the air brake system. Diagnostic schemes that will monitor the brake system for these defects will be presented and corroborated with experimental data obtained from the brake testing facility

In this paper, a scheme for estimating the proportion of the incoming traffic that is not responsive to congestion at a router is presented. The idea of the proposed scheme is that if the observed queue length and packet drop probability do not match the predictions from a model of responsive (TCP) traffic, then the error must come from nonresponsive traffic; it can then be used for estimating the proportion of nonresponsive traffic. The proposed scheme is based on the queue length history, packet drop history, and expected TCP and queue dynamics. The effectiveness of the proposed scheme over a wide range of traffic scenarios is corroborated using ns-2-based simulations. Potential applications of the proposed algorithms in traffic engineering and control are discussed.

In this paper, we show how a two-parameter compensator can always be designed for any Linear Time Invariant (LTI) plant, that does not have a zero at the origin, to render its step response non-overshooting.

In this paper, we propose a scheme for estimating the proportion of the incoming traffic that is not responding to congestion at a router. The idea of the proposed scheme is that if the observed queue length and packet drop probability do not match with the predicted results from the TCP model, then the error must come from the non-responsive traffic; it can then be used for estimating non-responsive traffic. The proposed scheme utilizes queue length history, packet drop history, expected TCP and queue dynamics to estimate the proportion. We show that the proposed scheme is effective over a wide range of traffic scenarios through simulations.