High-level intelligence in motion planning for unmanned aerial vehicles

Key publications (see also: complete list of publications)

Most unmanned aerial vehicles (UAVs) can already operate with some autonomy, for example, that of flying from one point to another without a (remote) pilot’s intervention. We study making UAVs perform more intelligent tasks, e.g. “search region A, if a target is found, then report the data to region C; in any case return to base B.”  The recent interest in cargo delivery leads to traveling salesperson-type problems involving multiple pickups and deliveries. How can we find UAV paths and trajectories to do such tasks? The challenges include limited onboard computational capability, and limited onboard fuel, which means that we must consider the optimality of paths and trajectories, and also computational efficiency in computing these paths and trajectories.

At the ACE Lab, we investigate two topics in this area. First, we address the generation of UAV trajectories to satisfy linear temporal logic (LTL) specifications. LTL is a formal system, similar to the commonly used propositional logic system. In addition to the standard operators “and”, “or”, and “not”, LTL includes temporal operators such as “always”, “eventually”, and “until”. LTL has been used in software design for specifying and verifying correct behaviors of algorithms. In recent years, LTL has also been used for specifying behaviors of mobile robots, and techniques to design control control laws that make the robot achieve the specified behaviors, have been studied.

Going beyond existing research, we address the satisfaction of LTL specifications by UAVs, whose motions are constrained. For example, fixed-wing aircraft have a minimum radius of turn. In the figures below, sample results of our algorithms indicate paths with minimum turn radii to satisfy LTL specifications on visiting colored regions of interest while staying clear of obstacles.

result_phi4_r3p5 result_phi5_r3p5 dubins_ltl_sampling

Interactive motion planning and sensing

Key publications

Autonomus vehicles rely on two major elements: (1) motion planning, or how to get from point A to B; and (2) sensing and estimation, or how to gather data and interpret the world. It is often convenient to treat these elements as separate problems and rely on a few assumptions to connect them later. Therefore, the planning problem may assume it has all necessary information, or that it has some certain level of information (uncertain or partial information). The sensing problem often assumes it needs to collect all possible information, typically the information maximization problem. Interactive planning and sensing aims to optimize the allocation of sensing resources given a particular planning task in a integrated and interactive manner.

The ACE Lab addresses this problem by understanding the interplay between the model of an environment, the ability to sense and estimate subdomains of that model, and the goals of the path planner. By identifying and isolating the effect of a model subdomain on the optimality of a path, we can allocate sensing resources to measure and verify the subdomain. This either confirms the path is optimal or reveals hidden risks or dangers, thus prompting the path planner to update the route.

A major benefit of this system is the robust performance with respect to high parameter systems using a limited pool of sensors. This becomes more beneficial as the complexity of models continues to grow, such as weather models or road and traffic pattern data. The nature of this approach allows users to tradeoff resources and objectives for a given situation. For example, specifying a higher requirement on path risk will require either more sensors or more time. However, given a certain requirement on path optimality, path risk, and model complexity, one can allocate the appropriate number of sensor resources. Likewise, given limited resources, one can get an expectation on the typical path performance given a certain model. The figure(s) below give an example of the typical process of Interactive Planning and Sensing.

ipas-iter-1 ipas-iter-2 ipas-iter-3 ipas-iter-4 ipas-iter-5

Selective listening in V2V communications

Key publications

  • N. Kanthasamy, R. V. Cowlagi, and A. M. Wyglinski. State Estimation for Mitigating Positioning Errors in V2V Networks Employing Dual Beamforming. Submitted to the 2018 Connected and Autonomous Vehicles Symposium, Chicago, IL,USA.
  • N. Kanthasamy, R. Du, K. S. Gill, A. M. Wyglinski, and R. V. Cowlagi. Assessment of Positioning Errors on V2V Networks Employing Dual Beamforming. Submitted to the 2018 IEEE 88th Vehicular Technology Conference: VTC 2018-Fall, 27–30 August 2018, Chicago, USA.

Self-driving cars already travel the roads. The next coming revolution in automobiles is of connected self-driving cars, which refers to connectivity among vehicles and connectivity between vehicles and infrastructure (traffic lights, pedestrians’ smartphones). Such connectivity will provide self-driving cars with a deluge of information, with the hope of significantly improved safety and reliability (e.g., two self-driving cars could avoid an impending collision if they could “talk and listen” to each other). However, wireless radio  communications technology imposes physical constraints on such connectivity, and only a small number of connections (less than 10) can be made simultaneously. On a typical urban road, there may be several dozens of cars within communications range. Therefore, the problem of selectively listening to a few among these dozens of other cars arises.

Such selective listening is relevant also from the perspective of motion planning and control. Self-driving cars have many different sensors carried onboard, which collect data about the nearby environment (e.g., pedestrians, road boundaries, lane markings, locations of other cars). V2V communications are additional sources of data for a self-driving car. However, with limited onboard computational capability, it is not practical to include data from all possible V2V communications. The premise of my newest research topic is that, practicality aside, it is not even necessary to include all V2V-communicated data. Similar to the discussion in previous sections, the motion planning problem for self-driving cars is coupled with the problem of identifying the most relevant data.

My work on this topic is in collaboration since Fall 2017 with Prof. Alexander Wyglinski at WPI-ECE.

Previous work: Accident analysis and system safety of hierarchical systems

Key publications

The risk analysis and system safety literature often reports on “organizational” accidents or “system” accidents in
sociotechnical systems. Whereas a “system theoretic approach” to accident analysis and safety has recently been advanced in the literature, formal system theoretic concepts of hierarchical and multilevel systems have been absent from the discussions of safety as a system theoretic problem. To address this gap, we introduce the concepts of coordinability and consistency from the analysis of hierarchical and multilevel systems to the risk analysis and system safety community, and we investigate the applicability of these concepts to system safety via an illustrative example.


Previous work: Randomized sampling-based optimal motion planning for self-driving cars

Key publication

Real-time motion planning techniques for autonomous terrestrial vehicles traditionally use low-fidelity, low-dimensional vehicle dynamical model. For high-speed driving, such methods are unable to use advantageously the vehicle’s full envelope of maneuvering capabilities. To remedy this problem, we investigate motion planning with the relatively high-fidelity half-car dynamical model. Specifically, we investigate the application of the RRT* optimal motion planning algorithm for this problem, and we develop a computationally efficient local steering algorithm – a crucial component in the RRT* algorithm.