Trajectory planning under motion and sensing uncertainties: reachability analysis and connectivity maintenance

Shetty, Akshay Prabhakar

Permalink

https://hdl.handle.net/2142/110464 Copy

Description

Title

Trajectory planning under motion and sensing uncertainties: reachability analysis and connectivity maintenance

Author(s)

Shetty, Akshay Prabhakar

Issue Date

2021-04-21

Director of Research (if dissertation) or Advisor (if thesis)

Gao, Grace Xingxin

Doctoral Committee Chair(s)

Bretl, Timothy

Committee Member(s)

• Makela, Jonathan
• Tran, Huy

Department of Study

Aerospace Engineering

Discipline

Aerospace Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• trajectory planning
• reachability analysis
• connectivity maintenance
• motion and sensing uncertainties
• autonomous robots
• collision avoidance
• collision safety
• alternating direction method of multipliers
• ADMM
• stochastic reachability
• GNSS planning
• unmanned aerial vehicles
• UAVs
• multi-robot systems
• multi-UAV system
• UAV swarms

Abstract

Recently there has been growing interest in robotic systems with several promising applications such as transportation, delivery of goods, surveillance and cinematography. Additionally, multi-robot systems are being increasingly considered for applications such as exploration, target tracking and formation control. A vital component of these robotic systems is planning trajectories that are collision-safe. Furthermore, for multi-robot systems it is highly desirable to plan trajectories that maintain communication connectivity within the system, thus enabling coordination between robots. For practical robots, trajectory planning is challenging due to the presence of uncertainties in robot motion and sensor measurements. These uncertainties result in the robot deviating from the planned trajectory and can consequently lead to collisions or loss of communication connectivity within multi-robot systems. Thus, it is important to explicitly account for motion and sensing uncertainties while designing trajectory planning algorithms. Reachability analysis is a popular verification-based tool where reachable sets for the robot are first computed along candidate trajectories and then used to plan collision-safe trajectories. However, previous works do not explicitly account for robot sensing uncertainties in their formulation. While there exist algorithms for trajectory planning under sensing uncertainties, these works model the uncertainties as known Gaussian distributions, which is not always valid. For instance, Global Navigation Satellite System (GNSS) pseudorange measurements may contain additional biases in urban environments due to non-line-of-sight signals or multipath effects. These biases in sensor measurements lead to further deviations from the planned trajectory and thus must be accounted for during planning. On the other hand, for multi-robot systems, the topic of connectivity maintenance has been explored in the literature. However, previous works assume simplified robot motion models and do not account for motion and sensing uncertainties in their formulation. The contribution of this dissertation is to develop trajectory planning algorithms that mitigate the aforementioned limitations in previous works. For planning collision-safe trajectories, we first develop a reachability analysis to predict possible robot deviations under motion and sensing uncertainties. We model the sensing uncertainties as a Gaussian distribution along with an additional bias. Next, we integrate the reachability analysis with an existing trajectory planning framework to plan collision-safe trajectories. Finally, we statistically validate via simulations that the reachability analysis captures the possible robot deviations. The applicability of the trajectory planner is then demonstrated for collision-safe GNSS-based navigation of fixed-wing Unmanned Aerial Vehicles (UAVs). For connectivity maintenance of multi-robot systems, we develop a distributed Alternating Direction Method of Multipliers (ADMM) based trajectory planner that explicitly accounts for motion and sensing uncertainties. We simulate a multi-UAV system and statistically validate that our planner maintains connectivity within the system for multiple scenarios.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/110464

Copyright and License Information

Copyright 2021 Akshay Shetty

Owning Collections