Imagine giving a drone a simple instruction:

Fly from one side of a warehouse to the other without hitting anything.

If the warehouse is empty, that is mostly a path-planning problem.

Add shelves and walls, and it becomes more interesting.

Now add people walking around, forklifts crossing aisles and objects that keep changing position.

Suddenly, finding a path is not enough.

The drone has to keep asking:

Will that path still be safe by the time I get there?

That was the problem I explored for my MSc Smart Autonomous Systems module.

I built a simulated environment, compared several established path-planning algorithms, and then developed a hybrid approach of my own:

PD*-APF — Predictive D* Lite with an Artificial Potential Field.

The key idea was straightforward.

Instead of planning only around where obstacles are, make the drone think about where they are going.

Why Moving Obstacles Change Everything

Consider a drone flying toward a corridor.

A person is walking across that corridor.

At the moment the drone calculates its route, the corridor is clear.

So the planner sees no problem.

But the drone takes time to move.

By the time it reaches the corridor, the person may have moved directly into its path.

The original route was technically correct when it was calculated.

It just became wrong before the drone could finish following it.

That is the fundamental difficulty of dynamic path planning.

In a changing environment, the best path is temporary.

Building the Test Environment

I created a 50 × 50 grid simulation representing the drone's operating space.

The environment contained fixed obstacles as well as moving ones.

To see how the algorithms behaved as the environment became more difficult, I tested three levels of dynamic obstacle density:

4 moving obstacles

8 moving obstacles

12 moving obstacles

Across the complete experiment, I ran 180 trials.

The goal was not simply to ask which algorithm produced the shortest path.

I also wanted to know which one could continue reaching its destination reliably as the environment became increasingly unpredictable.

Three Different Ways to Find a Path

Before developing the predictive approach, I compared three established planning algorithms.

Each solves the navigation problem differently.

A*: Find the Best Route Again

A* is one of the classic path-planning algorithms.

Given a start position, a destination and a map of obstacles, it searches for an efficient route through the environment.

For a static map, it works extremely well.

The problem appears when the map changes.

If a moving obstacle blocks the planned route, A* does not inherently reuse the work it performed previously.

It may need to calculate the path again.

You can think of it as someone planning a complete driving route, discovering that a road has closed, and then calculating the journey again from the new situation.

That works.

But in a constantly changing environment, repeated full replanning can become expensive.

D* Lite: Repair What Changed

D* Lite approaches the problem differently.

Instead of throwing away the entire plan whenever the environment changes, it tries to reuse previous search information.

If an obstacle invalidates part of the route, D* Lite can repair the affected portion.

Conceptually:

A*: "The map changed. Plan again."

D* Lite: "The map changed here. Repair the plan."

That makes D* Lite particularly attractive for robotics, where an autonomous system continually discovers new information about its surroundings.

But there is still a limitation.

Repairing a path after an obstacle moves is reactive.

The planner is responding to something that has already happened.

RRT*: Grow a Tree Through the Space

The third algorithm, RRT*, approaches navigation very differently.

Rather than systematically searching grid cells, it samples points through the available space and gradually grows a tree of possible routes.

Over time, it improves those routes toward a better solution.

This family of algorithms is particularly useful in robotics because it can operate in more complicated continuous spaces where grid-based search becomes difficult.

For my simulation, RRT* provided a useful contrast to the more structured A* and D* Lite approaches.

So I now had three baselines:

A* — search for an efficient path.

D* Lite — repair a path when the environment changes.

RRT* — explore the space through sampling.

Then I asked whether the drone could do something more proactive.

What If the Drone Looked Ahead?

Imagine watching someone walk across a room.

You do not normally avoid them based only on their current location.

You unconsciously estimate something like:

They are moving in that direction, so by the time I reach that point, they will probably be there.

That is a prediction.

It may not be perfect.

But even a short prediction can make navigation safer.

This became the central idea behind my hybrid planner.

PD*-APF

I called the approach PD*-APF.

The name describes the two main ideas behind it:

Predictive D* Lite

plus

Artificial Potential Field

The predictive component estimates where moving obstacles are likely to be in the near future.

Those predicted positions are then incorporated into the planning process.

Instead of asking:

"Is this cell safe now?"

the planner can effectively ask:

"Is this area likely to still be safe when I arrive?"

That changes the behaviour from purely reactive navigation toward short-horizon predictive navigation.

The Reactive Layer

Prediction is useful, but prediction can also be wrong.

A moving obstacle may:

  • change direction
  • slow down
  • accelerate
  • behave unexpectedly

So I did not rely entirely on forecasting.

The second part of the hybrid uses an Artificial Potential Field (APF) as a lightweight reactive mechanism.

The basic intuition behind an APF is easy to visualise.

Imagine the destination pulling the drone toward it while obstacles push the drone away.

The planner provides the broader route.

The reactive layer provides local avoidance.

So the system effectively operates at two levels:

Predictive planning → Where should I go?

Reactive avoidance → What should I avoid right now?

This combination was intended to handle both anticipated and unexpected movement.

Putting the Algorithms Against Each Other

I then tested:

  • A*
  • D* Lite
  • RRT*
  • PD*-APF

under the same simulated conditions.

The experiments looked at more than whether a path existed.

I recorded measures such as:

  • Success
  • Collisions
  • Path length
  • Planning time
  • Replanning behaviour
  • Smoothness

This was important because there is rarely a universally "best" navigation algorithm.

A planner might produce shorter paths but collide more often.

Another might be safer but computationally expensive.

Another might reach the destination reliably but produce awkward movement.

The useful question is therefore not simply:

Which algorithm wins?

It is:

Which trade-offs matter for the system being designed?

What Happened as the Environment Became Crowded

The most interesting result appeared as the number of moving obstacles increased.

PD*-APF achieved the highest success rate across the tested difficulty levels.

More importantly, its advantage became most visible as the environment became more crowded.

That was exactly the behaviour I was hoping to test.

Prediction offers limited benefit when almost nothing is moving around the drone.

When the environment becomes busy, anticipating movement becomes much more valuable.

In other words, the predictive layer became most useful when the navigation problem became hardest.

But I Didn't Want to Oversell the Result

It is very easy to build an experimental system, observe a higher average result and declare victory.

I wanted the statistical analysis to determine how strong that claim actually was.

The comparisons showed statistically significant differences between PD*-APF and some of the other planners.

Against D* Lite, the result reached statistical significance.

Against RRT*, the evidence was stronger still.

But the comparison with A* was different.

PD*-APF performed better on average in the experiments, but the difference was not statistically significant.

That distinction matters.

"Performed better in my trials" and "there is statistical evidence of a difference" are not the same statement.

A good experiment should be able to report both positive and inconvenient results.

Otherwise, it stops being much of an experiment.

Safety Wasn't Free

The predictive system also had disadvantages.

PD*-APF replanned more frequently.

Its trajectories could also be slightly less smooth.

That makes sense.

A planner that continuously responds to predicted obstacle movement is going to make more adjustments than one following a relatively stable route.

So the improvement came with a cost:

More replanning

More trajectory adjustment

Potentially less smooth movement

in exchange for:

Better collision avoidance and higher success in dynamic environments.

Whether that trade is worthwhile depends entirely on the application.

Which Would You Prefer?

Imagine two drones.

Drone A produces beautiful, smooth paths but occasionally fails when people cross its route.

Drone B adjusts its path more often and looks slightly less elegant, but reaches its destination more reliably.

For cinematography, smoothness might be extremely important.

For a warehouse drone operating around people, collision avoidance would probably dominate.

That is why optimisation in autonomous systems is rarely about maximising one metric.

Real engineering involves deciding which failures are acceptable.

Simulation Is Not Reality

There is also an important limitation.

This was a simulation.

A 50 × 50 grid is not a warehouse.

Simulated moving obstacles are not real people.

And a software drone does not experience:

  • sensor noise
  • localisation errors
  • wind
  • communication delays
  • actuator limitations
  • battery constraints
  • imperfect obstacle detection

A real autonomous drone would therefore require much more before this approach could be considered safe for physical deployment.

The value of the simulation is not that it proves the algorithm is ready for the real world.

It allows different planning ideas to be tested repeatedly under controlled conditions.

That is an important first step.

What I Would Explore Next

If I continued the project, one of the most interesting directions would be improving the prediction itself.

The current idea relies on short-horizon estimates of where obstacles are moving.

But real movement is rarely perfectly linear.

People stop.

They turn.

They interact with each other.

They change direction unexpectedly.

A more advanced system could investigate trajectory prediction using richer motion models or learned behaviour.

Another direction would be moving from a 2D grid into a true 3D environment.

That would change the problem substantially because a drone is not restricted to moving left, right, forward and backward.

It can also change altitude.

The extra dimension creates more escape routes — but also a much larger planning space.

What This Project Taught Me

The biggest lesson was not that one path-planning algorithm is universally better than another.

It was the difference between reacting and anticipating.

A purely reactive system asks:

"What changed?"

A predictive system asks:

"What is likely to change next?"

Neither is sufficient on its own.

Predictions can be wrong.

Reactions can come too late.

Combining the two creates something more interesting:

Plan for what you expect, but remain ready for what you didn't expect.

That principle goes well beyond drone navigation.

It appears in autonomous vehicles, robotics, logistics and many other systems that have to operate in environments shared with unpredictable moving agents.

For my simulation, prediction came with additional replanning and slightly less smooth movement.

I consider that an acceptable trade-off for the problem I was trying to solve.

Because when an autonomous system is moving through a crowded environment, the shortest or smoothest route is not necessarily the best one.

Sometimes the best path is simply the one that gets there safely.