AI Boot Camp

AI Boot Camp is an ensemble of AI coding challenges designed to teach the fundamentals of Symbolic AI.
This is how I knew that AI would became one of my greatest passions.

Agents must cooperate to avoid colliding with each other.

Description of the Challenge

The Rules

In AIBootCamp we must design an Artificial Intelligence that will be able to lead numerous Non Player Characters (Npc) into somes maps until they eventualy reach theirs goals.
Maps are sets of hexagons, named tiles, and a Npc can go from one adjacent tile to an other each turns.
Unfortunately maps are strewed with obstacles such as walls between two adjacent tiles or tiles that can be walked.
Maps can even contains doors, which seems rather harmless, but it isn't. In fact it was the main challenge across the entire problem.

What's more, our Npc don't always see all the map. In fact, most of the time, Npc have a vision range, this means that they only know of tiles that are near to them and that aren't behind walls. In that sens they act similarly to humans, and that's the whole point of this challenge.

Oh ! And did I mentionned that is was a group of Npc that we have to lead to theirs goals tiles ? This is also an increadible obstacle as Npcs can't walk onto another, so we have to create group behavior and politeness policy between them !

If you want to know more about the challenge in details, here is the link to the website of the challenge ! : )

Technical challenges

In AIBootCamp there a lot of different challenges that we had to overcome, here is a list of a few of them :

- Modeling : In order to take good decision, we have to create a Model from our sensors in which we can think.
- Planning : We have to decide for each Npc what to do every turn. But we want them to have coherent actions in time, so we need to plan ahead.
- Pathfinding : We need ours Npcs to find a path to a target, whether it' s a goal or not.
- Collaboration : We want that Npcs collaborate in a way that optimize time and efforts of them globaly.
- Politeness : We want that them to act inteligently and not rushing into each others.
- Exploration : As we don' t know the map in advance, we need them to gather informations about the world in order to take better decisions.
- Oriented Exploration : But we need some informations more than others, so we prioritize exploration.
- Interaction : We need to be able to open doors, or to stay on door activator switch until another (or several) Npc cross the door.
- Adaptability : We needed to construct a model such that we can add new features easily. Maybe we now have to dodge some guards ? Well, it' s doable in our model !
- Performance : As in every video game, we have time constraints, so we need to be lightning fast, even if we don' t reach the best solution each time. That' s heartbreaking to me, but at least we always find a solution (and very often one of the best !).

Iterations of the project

We first start this project alone, then after a first iteration essentialy focusing on pathfinding, we merge into team of 3 peoples. The project was now focused on cooperation and multiple Npcs planning. We then split the team and merge again in teams of 5 peoples. I had the chance that we keep my code as a solid base to continue work together each time. Now the project was focusing on improving performances, up to 15 milliseconds ! Finaly, we had a last iteration focused both on optimisation - we have to go up to 5 milliseconds ! - and the integration of a nightmarish and beautiful element : the doors ! <3

Here an example of a rather complicated map, espacialy because of his size ! :)
Our algorithm find an optimal solution, can you ? (don't forget that NPCs have a vision range of 5!)

How we solve it !

We had the chance to have testing maps, which you can observe on the website. They helped us to focused on what was a problem and to found edges cases. However the final goal of this entire project was to be able to achieve maps that we would never have seen before !!!

In order to emphasize this our amazing teacher Carl Côté created 10 secrets maps and told us that we will never seen them until we try them for the final test ! This kind of approache motivate me a lot during all the course of the project, and I think this is why we made such good results in the end.

Finaly, we would end up solving 9 out of 10 of the secrets maps !!! I was sooo happy ! <3 Especially when I noticed that our teacher only solved 8 of them ! Even if there is a rational explication to this (our teacher used the same algorithm as last year because of a lack of time, however he add an harder time constraint that he didn't have last year, that's why his algorithm wasn't fully apropriate), this event fulfilled me ! :)

If you want to understand our algorithm in details, please go check our paper here :

You can also find our presentation here :