6G7V0011- Search Algorithms in Artificial Intelligence Research and Industrial Applications: Artificial Intelligence Principles, Assignment - MMU

Aim

This assignment provides a case study that involves a searching module, to give you the experience of implementing and applying search algorithms you’ve learned from this unit. The case study is about mobile robot path planning, which is a key component for mobile robot navigation. You may think of examples such as autonomous vehicles finding a path from your current location to your destination, or simply a robot cleaner finding the path from its current location to a certain area in your house to do cleaning work.

A mobile robot, ‘is a robot that is capable of moving in the surrounding.’ Mobile robots are frequently required to move from one location A to another location B. Before moving, they need to find the ‘best path’, which is usually the one that costs the least time or energy, etc. The ‘best path’ is mostly found by a search algorithm.

In real life, mobile robots are three-dimensional (3D) objects moving in 3D environments. In this coursework, we focus on the search algorithm aspect, which enables us to simplify the problem. One way to do simplification is projecting the height of a robot (z-axis) to the plane comprised of the x and y axes. Figure 1 gives such an example. Note this projection does not change the dimensions of the robot (width and length if the robot has a rectangular base and radius for a robot with a circular base).
Therefore, we still need to consider the shape and the size of the robot in this 2D environment.

Figure 1 demonstrates how the 3D environment is simplified. The 2D environment is divided into grids. There are two types of grids, i.e., yellow ones indicating free space where the robot can move, and black ones indicating obstacles where the robot cannot move. The task is to find a path from A (initial state, marked in red) to B (goal state, marked in green) in the free space.

Figure 1. Projecting a 3D environment to a 2D one. The 2D environment is divided into grids. The robot can move in free space indicated by free grids. The robot cannot move over grids that are occupied by obstacles.

Assessment Overview (1CWK100)

As a group, you will need to implement search algorithms such as Breadth First Search (BFS), Depth First Search (DFS), Uniform Cost Search (UCS), and A Star (A*) search learned from this unit and apply them to find the ‘best’ path for a mobile robot navigating in a 2D environment. The algorithms should be
implemented following both the `tree search’ paradigm (Set 1) and the ‘graph search’ paradigm (Set 2). The performance of different algorithms within each Set and across the two Sets will be evaluated and compared. By finishing this coursework, you should learn to formulate the searching module for a real problem (robot navigation in this case), pick the right search algorithm from search algorithms and implement it for a specific problem.

To make this coursework a learning experience (as well as an assessment), I have provided extensive scaffolding taking you through the tasks you have to perform. The details are as follows:

1.    Understand the principles of BFS, DFS, UCS, and A*

2.    Design your robot and environment

a.    Understand the mobile robot path planning task.
b.    You should design the shape and size of your robot. For instance, if your robot is of a circular base, then your robot should be represented by a circle with a radius of 0.2 m (you can modify the radius as you like) in a 2D environment.
c.   You should design the motion model of your robot; each motion should come with a cost. An exemplar motion model is given in Figure 2, where the robot can only move up, down, left, and right, with a cost of 1 for each move.

Figure 2. An exemplar motion model. The elements in (x,y, cost) are as follows: x: the x coordinate; y: the y coordinate; cost: the cost of the current move. Note one ‘move’ means move one step away from the current location, to move up, down, left, or right.

d.  You should design your environment. A grid environment as shown in Figure 1 will do the job. You need to design the shape (such as square) and the size of each small grid, where to pose the obstacles, and whether you need a border for the environment, etc.
e.  You should specify the initial state and goal state.

3. Structure your environment. The environment can be represented by a binary matrix. Each entry of the matrix corresponds to a grid of the environment. When the entry value is 0, it means the corresponding grid is free for the robot to move. When the entry value is 1, it means the grid is occupied by obstacles. You can visualize your environment, or simply print out the matrix to check if it is properly structured.

4. For A* algorithm, you should design a heuristic function as well. Consider about Euclidiandistance or Manhattan distance. For BFS, you should bear in mind that the motion cost should be equal in each direction.

5.  Search algorithms application:
a. A template environment will be provided. You can either modify the template to deliver your project or do it completely from scratch. The marking scheme will vary.
b. Tree search
i. Implement BFS, DFS, UCS, and A*. You should record the path found and time elapsed.
ii.  The paths found by each algorithm can be visualized separately or simply superimpose them onto the environment.

lines show the path exploring history and the black line shows the final path. The red square is the initial state, and the green square is the goal state. Cyan squares are free and gray squares are obstacles and borders of the environment.
c.  Graph search
i.    Implement BFS, DFS, UCS, and A*. You should record the path found and time elapsed.
ii.    The paths find by each algorithm can be visualized separately or simply superimpose them onto the environment.
d.    Analyze the memory/storage consumption by each algorithm.

6. Compare the path and time obtained by the above two sets of algorithms. A report should be written to analyze the results. The skeleton report is given in the appendix.

7.  Further reflection and discussions about the performance of the algorithms.