A Knowledge-based AI Agent
My agent class is implemented in MyAI.cpp and MyAI.hpp.
I use a two dimensional board vector to maintain the state at each position. The agent senses the environment around its position when it is moving forward, and updates the knowledge base. It keeps track of where it’s already been and which next step is safe to go. When it senses stench or breeze, then the next cell could be dangerous and it turns back and returns to the starting position using breadth first search algorithm.
Compared with my draft AI algorithm, I made improvements in the following aspects:
(1) Added a safe flag to each position in the board. Any visited position is safe. If there is no stench or breeze, then the valid surrounding neighbors of the current position are safe. These two rules are used to update the safe status of board positions.
(2) The agent will use the recorded safe and visitCount flags to determine the action it should take. If there are no safe neighbors, the agent will start searching for the return path and return its start position. If there are one or more neighbors that are safe, the agent will visit the position that has not been visited. In priority, the agent will check the facing neighbor first as the cost of moving to the facing neighbor is the least. If the facing neighbor is not safe, then it will check left neighbor and right neighbor. If both the left and right neighbors are safe, then it will randomly pick on neighbor as the next position.
(3) Added least cost distance search algorithm to search for the return path of minimum cost. I used a breadth-first search algorithm to calculate the accumulative cost of moving from the return position to the visited positions. The algorithm calculates the number of steps of moving from the current position to the visited neighbor positions, and updates the accumulative cost of the neighbor position if the accumulative cost from current position is lower than the accumulative cost from other positions. This least cost distance algorithm is supposed to return a path that has the least accumulative cost. This algorithm increases the agent scores in the tests.
(4) Lastly, I added a variable numSteps to record the number of steps the agent has taken so far. If the numSteps exceeds a certain number, then it will stop searching. This prevents the agent from getting to an infinite search. I chose the threshold of 100 as it gave a higher score compared with other thresholds.