⚡ electrical engineering

Obstacle-Aware Four-Dimensional Trajectory Design for Urban Air Mobility

This paper proposes a hybrid framework that integrates urban obstacle data, wind conditions, and eVTOL flight dynamics to generate safe, time-optimal four-dimensional trajectories for Urban Air Mobility, demonstrating that neglecting these real-world constraints can lead to significant underestimations of flight time.

Original authors: Prasad Devkar, Yashovardhan S. Chati, Arunchandar Vasan

Published 2026-07-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Prasad Devkar, Yashovardhan S. Chati, Arunchandar Vasan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the sky above our cities is about to get a whole lot busier. Instead of just planes soaring high above the clouds, we're talking about a new kind of traffic: tiny, electric flying cars called eVTOLs (electric Vertical Take-Off and Landing vehicles). These aren't sci-fi dreams; they are real machines designed to zip people around cities, dodging the gridlock on the ground below. But here's the tricky part: flying low over a city is like trying to thread a needle while riding a unicycle through a forest of skyscrapers. You have to avoid crashing into buildings, deal with gusty winds, and make sure your battery doesn't die before you land. If you plan the flight path wrong, you might waste precious time, run out of power, or worse, hit a building. So, scientists are trying to figure out the perfect "4D" route for these flying cars—a path that includes where to go (latitude and longitude), how high to fly (altitude), and exactly when to be there (time).

This paper tackles the massive puzzle of how to design these safe, fast, and energy-efficient routes for electric flying cars in a crowded city. The authors, working with data from New York City, realized that old ways of planning these flights were missing the mark. They built a new, smart system that acts like a super-planner, combining a few different tricks to find the best path through a maze of buildings and wind. They found that if you ignore the messy reality of wind and buildings, you might think a trip will take 20% less time than it actually does. Their new method doesn't just guess; it calculates a precise path that keeps the flying car safe and on time, even when there are hundreds of buildings in the way.

The Problem: Flying Through a Concrete Jungle

Think of planning a flight for an eVTOL like trying to draw a line through a dense forest without touching a single tree. In the past, scientists tried to solve this in two main ways, and both had flaws.

The first way was like playing a video game on a grid. You break the sky into tiny squares and use a simple algorithm to find the shortest path from point A to point B. It's fast and easy, but it treats the flying car like a robot that can instantly stop and turn. It ignores the fact that real flying cars have weight, momentum, and engines that take time to react. It's like telling a heavy truck to make a U-turn in a parking spot the size of a bicycle; the math says it's possible, but physics says no.

The second way was to use a super-complex math model (called an Optimal Control Program, or OCP) that knows everything about the flying car's physics. This model is great at understanding how the car moves, but it struggles with the "forest" of buildings. When you tell this model to "avoid every single building," the math gets incredibly messy and confusing. It's like trying to solve a maze where every wall moves. If there are too many buildings (like 250 in a city like New York), the computer gets stuck and can't find a solution at all. It's a "nonconvex" problem, which is a fancy way of saying the path is full of dead ends and traps that confuse the solver.

The Solution: A Hybrid "GCS-OCP" Framework

The authors of this paper came up with a clever hybrid solution they call GCS-OCP. Instead of trying to avoid every single building directly, they flipped the problem on its head.

Step 1: Map the Safe Zones (The "Clearing" Strategy)
Imagine you are in a forest, and instead of looking at every single tree to avoid, you look for the big, open clearings between them. The researchers used a tool called IRIS to find these "clearings" in the sky. They filled the empty space between buildings with overlapping, safe, convex shapes (think of them as giant, invisible bubbles or polygons). If your flying car stays inside these bubbles, it is guaranteed not to hit a building. This turns a messy "avoid everything" problem into a clean "stay inside these shapes" problem.

Step 2: Find the Best Route (The "Graph" Strategy)
Next, they built a map (a graph) connecting these safe bubbles. Using a method called Graph of Convex Sets (GCS), they quickly figured out which sequence of bubbles would get the car from the start to the finish the fastest. It's like a GPS that knows which highway exits to take to avoid traffic, but instead of roads, it's hopping from one safe bubble to the next. This step gives them a "candidate list" of a few good routes.

Step 3: The Final Polish (The "Physics" Strategy)
Finally, they took those candidate routes and fed them into their super-complex physics model (the OCP). Because the model now only has to keep the car inside the safe bubbles (instead of dodging 250 individual buildings), the math is much easier to solve. The model then calculates the exact speed, tilt, and power needed to fly through those bubbles, accounting for wind and the car's battery limits.

What They Found

The researchers tested their new framework on routes in New York City, flying from various points to JFK Airport. They simulated flights at different heights, dealing with anywhere from a few dozen to 250 building obstacles.

Here are the big takeaways from their simulations:

The "20% Surprise": If you plan a flight without considering the wind, the buildings, or the car's real physics, you might think the trip will take a certain amount of time. But in reality, the trip could take 20% longer. That's a huge difference for a flying taxi service!
Better than the "Direct" Way: Their new hybrid method (GCS-OCP) consistently found faster routes than the old "Direct OCP" method. In some cases, the old method took 22% longer or simply failed to find a route at all because the math got too complicated.
Scaling Up: The old method broke down when there were too many obstacles (around 250 buildings). The new method handled 250 obstacles like a champ, proving it can scale up for real, dense cities.
Smart Detours: The system learned that sometimes the fastest way isn't a straight line. It would weave the car between buildings (using the safe bubbles) rather than going all the way around them, saving precious time.

The Catch and the Future

The authors are careful to note that their system is currently a "offline" planner. This means it takes a bit of time to crunch the numbers (sometimes over a minute or two on a standard computer), so it's great for planning a route before you take off, but maybe not for making split-second changes while you are already flying. Also, their simulations assumed the wind was steady and the buildings were stationary. In the real world, wind gusts change, and other flying cars might be moving around.

However, this work is a significant step forward. It shows that by combining a smart map of safe zones with a physics-aware engine, we can design flight paths that are not just safe, but actually efficient. As cities get busier and the sky gets crowded, this kind of "smart navigation" will be the key to making Urban Air Mobility a reality that we can all trust.

Technical Summary: Obstacle-Aware Four-Dimensional Trajectory Design for Urban Air Mobility

Problem Statement

The rapid growth of Urban Air Mobility (UAM) utilizing electric Vertical Take-Off and Landing (eVTOL) vehicles presents a solution to ground traffic congestion but introduces significant operational challenges. A primary challenge is the design of safe, four-dimensional (time, latitude, longitude, altitude) trajectories that minimize travel time while navigating dense urban environments.

Existing trajectory design methods suffer from specific limitations:

Graph-based planners often operate at a kinematic level, failing to explicitly model complex eVTOL flight dynamics, actuator limits, or energy consumption, leading to potentially infeasible trajectories.
Optimal Control Program (OCP) approaches explicitly model dynamics but often neglect obstacle constraints. Directly embedding non-convex obstacle avoidance constraints into an OCP creates highly non-convex problems that struggle with convergence and scalability in environments with many obstacles.
Hybrid approaches exist but frequently treat flight phases separately, neglect wind effects, or rely on simplistic curve fitting (e.g., Bézier curves) that cannot easily enforce complex dynamic constraints.

Consequently, current methods may produce low-quality or infeasible trajectories and can significantly underestimate flight time by failing to account for wind, dense building obstacles, and nonlinear dynamics across ascent, cruise, and descent phases.

Methodology: The GCS-OCP Hybrid Framework

To address these gaps, the authors propose a unified hybrid framework, GCS-OCP, which integrates obstacle data, wind fields, eVTOL flight dynamics, and operational constraints to design end-to-end trajectories. The framework operates in three distinct stages:

1. Convex Decomposition of Obstacle-Free Space

Instead of treating obstacles as non-convex constraints to be avoided, the framework identifies the complementary obstacle-free regions.

Grid Generation: A 2D horizontal grid is generated in the cruise plane between the start and end points.
Obstacle Identification: Building footprints exceeding the cruising altitude (plus a vertical safety buffer) are identified as polygonal obstacles.
IRIS Algorithm: The Iterative Regional Inflation by Semi-definite programming (IRIS) algorithm is used to decompose the obstacle-free space into a collection of intersecting convex polygons. This transforms the obstacle avoidance problem into a convex containment problem.

2. Graph-Based Path Planning (GCS)

A Graph of Convex Sets (GCS) is constructed where nodes represent the convex polygons and edges represent intersections between them.

Edge Weighting: Edges are weighted by the estimated travel time between polygons, accounting for wind effects on ground speed.
Candidate Sequence Selection: A GCS-based planner solves a relaxed mixed-integer convex program to identify a small set of candidate sequences of polygons that connect the start and end points. This step provides a high-level guidance path through safe corridors without solving the full dynamic optimization yet.

3. Optimal Control Program (OCP)

For each candidate polygon sequence, a detailed OCP is solved to generate the final dynamically feasible trajectory.

Convex Containment Constraints: The cruise phase is partitioned into segments, with each segment constrained to lie within a specific convex polygon from the candidate sequence. This replaces non-convex obstacle avoidance with convex containment constraints.
Dynamic Constraints: The OCP explicitly models nonlinear eVTOL dynamics (including rotor thrust, drag, and induced velocity), actuator bounds, battery energy consumption, and passenger comfort constraints (acceleration limits) across all three flight phases: vertical ascent, level cruise, and vertical descent.
Optimization: The objective is to minimize total travel time ( $t_F$ ). The framework iterates through candidate sequences and discretization intervals to find the trajectory with the minimum flight time.

Key Contributions

Unified Hybrid Framework: The paper introduces a novel GCS-OCP framework that unifies global path planning (via GCS) with local trajectory optimization (via OCP) to handle dense obstacles, wind, and complex dynamics in a single workflow.
Scalable Obstacle Handling: By reformulating obstacle avoidance as a sequence of convex containment constraints rather than non-convex avoidance constraints, the framework scales effectively with the number of obstacles (demonstrated up to 250 obstacles), whereas direct OCP formulations often fail to converge.
Comprehensive Constraint Integration: The framework simultaneously accounts for wind fields, building obstacles, nonlinear flight dynamics, and operational limits (battery, actuator, comfort) across ascent, cruise, and descent phases.
Performance Validation: The authors demonstrate that ignoring realistic constraints can lead to underestimating flight time by up to 20%.

Results and Evaluation

The framework was evaluated on routes within New York City (NYC) connecting various origins to John F. Kennedy International Airport (JFK), using real-world building footprint data and constant wind fields.

Flight Time Accuracy: Comparisons with a "back-of-the-envelope" baseline (ignoring wind and obstacles) and a Direct-OCP (D-OCP) approach showed that the GCS-OCP framework yields more accurate flight time estimates. Ignoring constraints underestimated flight time by up to 20%.
Optimality vs. D-OCP: The GCS-OCP framework produced trajectories with lower travel times (up to 22% faster) compared to D-OCP in scenarios where D-OCP converged. This is attributed to the ability of GCS-OCP to find efficient paths through obstacle-free corridors rather than getting trapped in local minima caused by non-convex constraints.
Scalability: The framework successfully generated trajectories for scenarios with up to 250 building obstacles. In contrast, the D-OCP formulation failed to converge (Did Not Converge - DNC) in many high-obstacle scenarios due to the non-convex nature of the constraints.
Computational Trade-off: While the total runtime of the GCS-OCP framework is higher than a single D-OCP run (due to the overhead of IRIS and GCS planning), the underlying OCP solver (IPOPT) for GCS-OCP is computationally more efficient for high obstacle counts. As the number of obstacles increases, the number of variables and constraints in D-OCP grows significantly, whereas GCS-OCP maintains a more manageable problem size by restricting the search space to convex polygons.

Significance and Claims

The paper claims that the GCS-OCP framework offers a robust and scalable solution for UAM trajectory design in dense urban environments. Its primary significance lies in bridging the gap between global path planning and dynamic trajectory optimization, ensuring that generated trajectories are not only collision-free but also dynamically feasible and operationally realistic.

The authors emphasize that neglecting factors such as wind, obstacles, and complex dynamics leads to sub-optimal air corridor planning and inaccurate energy/time estimates. By enforcing trajectories to pass through identified safe regions, the framework achieves a balance between computational tractability and solution quality, enabling the design of efficient eVTOL routes even in highly cluttered cityscapes.

Limitations Acknowledged:
The authors note that the current framework is suitable for offline planning rather than real-time re-planning due to solution times. Additionally, the current implementation assumes static, uniform wind fields and stationary obstacles, excluding dynamic wind variations and moving obstacles (e.g., other aircraft). The solution is also not guaranteed to be globally optimal due to the nature of Nonlinear Programming (NLP) solvers.