FIT3094 - Artificial Life, Artificial Intelligence, and Virtual Environments - ASSIGNMENT 1: Multi-Agent Pathfinding
FIT3094 - Artificial Life, Artificial Intelligence, and Virtual Environments
ASSIGNMENT 1 Multi-Agent Pathfinding
SUBMISSION DUE: Friday Week 4, 11:55 PM Covers Topics from Weeks 2 - 4
Learning Outcomes
Completion of this assessment item should demonstrate competency in the following learning outcomes: ● Apply - through practice-based learning - design, development, execution and validation of real-time interactive software using AI techniques ● Evaluate and apply AI and/or ALife software techniques to model simple intelligent behaviour in discrete and continuous simulations and games ● Explain the concepts and theories underlying AI and Artificial Life;
Brief
For this assignment, you will be managing the pathfinding component of multiple agents to navigate to treasure within a virtual environment. This agent and the environment will be provided within base code for the project, and the focus will be the implementation of active pathfinding. The virtual environment will be fully observable to the agent, and within a discreet world.
Task Overview
All of the ships have to find their own treasure in a virtual environment, navigate to it, and then wait for every other ship to finish. There are multiple scenarios that you will have to solve with an increasing number of ships.
Your task is to implement algorithms for pathfinding that assist the ships in finding treasure and avoiding collision between other ships.
Marks will be allocated for:
- Documentation and Coding Standards
- Pathfinding Algorithm Effectiveness & Efficiency
- Collision Avoidance Efficiency
Detail on each of the requirements for points 1-4 above and the marks allocated to each component, appear in sections below.
You have been provided with base code that contains starter files to assist you in developing your pathfinding algorithms. The base code does the following:
- Loads a map file and converts it into an Unreal level
- Loads a scenario file and spawns ships based on the scenario
- Automatically progresses to the next level as soon as all ships reach their goal
- Handles ship movement based on a path given to it
- Outputs heuristic data to help you with fine-tuning your algorithms
The base code does not handle behaviour for avoiding collisions and replanning. This must be performed as part of your implementation of the pathfinding and collision algorithms.
Documentation and Coding Standards
Suggested Completion Date: End of Week 4
You must ensure that you include a written justification of your choice of algorithms and that your code is properly formatted with appropriate use of comments and conventions.
This includes: ● Written Justification of Chosen Algorithms ● Comments, Naming Conventions, Variable Names, and Readability of Code
Written Justification of Chosen Algorithms
As part of the Pathfinding and Collision Avoidance sections of this assignment, you will be required to implement some algorithms. You will be required to include a text file with your justification for both your pathfinding algorithm and collision avoidance algorithms. This should include additional research and justification in line with what you have learned in the lectures. This should include: ● Performance and Suitability to this task ○ Completeness ○ Optimality ○ Optimisation ○ Performance ● Comparison data
Comments, Naming Conventions, Variable Names, and Readability of Code
You will be required to make sure that your code uses appropriate variable names which represent what the variables are being used for, consistent naming conventions, as well as overall code readability. On top of this, you must ensure that all the code solution is commented thoroughly, including the base code, to show your understanding.
Pathfinding
Suggested Completion Date: End of Week 3
You will be required to solve a series of multi-agent scenarios which will increase the amount of ships as they progress. The scenarios are as follows:
● Scenario 1: 1 Ship ● Scenario 2: 2 Ships ● Scenario 3: 5 Ships ● Scenario 4: 10 Ships ● Scenario 5: 25 Ships ● Scenario 6: 50 Ships ● Scenario 7: 100 Ships
You will be required to generate paths for every ship in each scenario, and you will be marked on the following categories for each scenario:
● Effectiveness of Chosen Algorithm ● Efficiency of Chosen Algorithm
Effectiveness of Chosen Algorithm
You will be marked based on how many scenarios your pathfinding algorithm can handle, for each milestone you complete, you will receive a higher mark. This breakdown is shown in the detailed rubric on Moodle.
Efficiency of Chosen Algorithm
You will be marked based on how efficiently your chosen algorithm performs in each scenario. At the start and end of each scenario, the base code will output some heuristic information from your search. You will receive marks for each milestone you complete in respect to:
● Total Cells Expanded ● Total Path Cost
This breakdown is shown in the detailed rubric on Moodle.
Collision Avoidance
Suggested Completion Date: End of Week 2 You must implement collision avoidance for the ships to avoid ships either sharing the same grid node, or swapping grid nodes. Your task will be to optimise this collision avoidance algorithm as well as you can to minimise the difference in your planned path cost and your actual path cost.
Assessment Criteria
Documentation and Coding Standards - 20 marks ○ Written Justification of Chosen Algorithms included in submission ○ Use of Comments throughout code ○ Use of consistent Naming Conventions throughout code ○ Use of consistent Variable Names that are indicative of their purpose ○ Readability of Code ● Pathfinding - 50 marks ○ Effectiveness of Chosen Algorithm – Based on how many scenarios can be completed ○ Efficiency of Chosen Algorithm through benchmarks based on Path Cost and Cells Searched ● Collision Avoidance - 30 marks ○ Actual Path Cost vs Planned Path Cost - Based on ratio of Actual Path Cost / Planned Path Cost A detailed marking rubric is provided on Moodle.
