Influence Based Pathfinding

The Problem

We wanted to create a pathfinding algorithm that would be more applicable to real environments. Current pathfinding algorithms find the shortest paths in static environments. However, we, as humans, may not always be looking for the shortest paths. We choose ours paths based on various factors, like interest, visibility, and crowdedness. Our environment is always changing due to traffic, infrastructure, and congestion too.

Could we make an agent avoid large congestions even though it's the shortest path? Or, an agent that will only move to areas it can clearly see?

My Process

I was one of the main programmers for this project. 

I first started with implementing the HPA* algorithm, a pathfinding algorithm. The algorithm had to run in a virtual environment in Unity, which my PI provided for us. Though it sounds simple, this task with difficult for me. The documentation for HPA* was abstract and I could not find many resources to help me. This was my first job in a professional environment too. I had to push myself and leave my comfort zone to implement the algorithm. It took awhile for me to finish it!

When this was completed, other programmers joined our team. They were the researchers behind influence maps, a tool implemented to simulate factors that would influence pathfinding agents. We worked together to integrate their influence maps with the HPA*.

We finished up by making the environment more realistic. I programmed specific behaviors for the agents so that they looked like they were patrons of a hospital. 

The Results

The result was a working demo of agents navigating through congestions. We were sadly unable to expand it further to include other external stimuli, like visibility. However, I had the opportunity to present this to the Undergraduate Research Symposium as first author.

My Takeaways

• As my first programming job, I learned:

  • Communication IS PIVOTAL! This includes:

    • Being honest with your team.

    • Being detailed oriented.

    • Setting work-life boundaries with your team members.

  • How to take responsibility for your work.

  • Teamwork skills.

  • That documentation is helpful for everyone - including you!