Reference no: EM133684098 , Length: word count:2000

Introduction to Artificial Intelligence

Objectives

This assignment is designed to reinforce the knowledge and skills acquired in Week 5 to Week 7. It is an individual assessment to be submitted in Week 8. The assessment task relates to Unit Learning Outcomes 1, 2 and 4, and must be done and submit individually.

Problem Description
Bakers Fresh, a local bakery in Brisbane, prides itself on delivering freshly baked products to its loyal customers. As the customer base grows, planning optimal delivery routes for its trucks has become increasingly challenging. Currently, the bakery relies on a manual process for assigning deliveries to its drivers. This often leads to sub-optimal routes, resulting in longer delivery times that has negatively impacted customer satisfaction.

To address this problem, Bakers Fresh is hiring you to develop a more efficient method for planning the delivery routes. As an example, figure 1 shows how delivery routes may be seen as paths in a graph. The numbers on the edges denote the distances between pairs of locations.

Tasks
Part 1: Modelling and Algorithm Design

Problem Modelling:
Explain how the delivery scenario can be modelled as a graph. Identify nodes and edges and their meaning in the context of the problem.
Consider the choice of data structures for representing nodes and edges. Explain your choice. If the choice of data structures is different for both uninformed and informed search algorithms, explain the difference.

Algorithm Design:
Design an algorithm based on A* search to find the shortest delivery route. Include pseudo code with comments explaining the major steps of the algorithm.

Briefly discuss the heuristic function that you are using in the A* search.

Choose an uninformed search algorithm you have come across as the candidate to compare with the A* search. Explain this uninformed search algorithm.

Part 2: Implementation

Python Implementation:
Implement the A* search algorithm in Python using your chosen data structures.
Implement the uninformed search algorithm in Python for comparison.
Ensure your code is well-documented and includes comments explaining your logic.

Test Data Design:
Design the test data, including at least 20 delivery locations (discounting the location of Bakers Fresh), for the comparison.
Include the test data in your Python code.

Part 3: Testing and Analysis

Testing:
Test your implemented algorithms (A* and chosen uninformed) with the designed test data.
Capture screenshots of the test output from your Python program for both algorithms.
Analysis:
Compare and analyse the performance of both the A* and the uninformed search algorithm in terms of:
Efficiency (number of nodes explored)
Optimality (shortest route found)
Other relevant performance metrics you can think of
Discuss which of A* search and the uninformed search performs better in the specific problem of this assignment. Why?

Part 4: Reflection

Reflection:
Summarise your learnings from this assignment.
Reflect on the strengths and limitations of the implemented algorithms.
Propose potential improvements on either or both algorithms.