Individual Project: Search and Bayesian Update (7COM1034)

This project showcases a Python implementation of search algorithms and Bayesian updates within the context of an Artificial Intelligence coursework. The project tackles two core problems: the decanting problem and a whale watching scenario. The decanting problem involves developing a solver to determine the steps required to measure a specific amount of liquid using vessels of different capacities. The whale watching problem simulates a ship navigating a 10x10 grid, employing Bayesian updates to refine the ship's model based on distance measurements. The project includes literature review on search algorithms and state identification, pseudocode, and detailed algorithms for solving both the Minesweeper and whale watching problems. The solution demonstrates the application of search techniques to find solutions and Bayesian methods for updating beliefs in uncertain environments, providing a practical exploration of AI principles.

Programming

Table of Contents
Introduction...............................................................................................................................................1
Literature Review for Search algorithms and state identification.........................................................1
Search algorithms..................................................................................................................................1
State Identification................................................................................................................................2
Double Problem of Searching and Identifying State...............................................................................2
Pseudo code............................................................................................................................................3
Algorithm for Minesweeper problem and Whale watching problem....................................................3
Algorithm for Minesweeper problem...................................................................................................3
Algorithm for Whale watching problem..............................................................................................4
Conclusion..................................................................................................................................................4
References..................................................................................................................................................5

Introduction
In this project to implement the search decanting problem and Bayesian update using
python code. To apply the search algorithm for search the particular value from given data. The
first task is to solve the decanting problem from given data and search the particular data using
python source code. It has the initiate state value and target state value for solve the problem. In
second task is to simulate a ship trying to reach a whale in a 10 X 10 grid world using python
code. It has the 10 x10 array gird world both x and y coordinate are numbers from 0 to 9
inclusive. We have apply the distance measurement formula for update the Bayesian and show
that ship model value.
Literature Review for Search algorithms and state identification
Search algorithms
According to this paper (Hacker Noon, 2019),
In search algorithm they are programmed to perform a particular action for a particular
state. To identify the action or series of actions that lead to the goal. To evaluate a solution and
determine its preference for achieve that goal. Search algorithm using to search the particular
value or series form given data. It is used to model the sequence of actions which constructed
with initial state as the root. It has the three region for searching such as explored, frontier and
unexplored. There are two types search involved on search algorithm such that uniformed search
and informed search. Uniformed search based on the breadth first search, depth first search,
depth limited search and iterative deepening search (Chlond, 2011). The informed search based
on greedy search and A star search for calculate the minimum cost.
State Identification
i) Initial state
It is an initial condition of the problem and it is start stage to continue the problem.
ii) States
The agent take the all possible state and all stares that are reachable from initial state by any
sequence of actions.
iii) Actions
The agent can perform in a particular state.

iv) Transaction Model
In a particular stare which describe the results of each action.
v) Goal Test
To check whether it achieve the goal or not.
vi) Path Cost
That assigns a numeric cost to path using function.
Double Problem of Searching and Identifying State
Consider a 2D grid that having the several obstacles and it start from initial to reach the
goal. The A* search algorithm used to path findings and graph traversal. In first step pick the
node according top initial state value and that state having the two parameters. The first
parameter using to move form initial state to given square on the grid that following the path
generated. In second parameter to find the distance between the initial states to target state. It
find the Manhattan distance and diagonal distance for 2D grid world. Manhattan distance is
calculate the distance between the x coordinates and y coordinates value. It main goal is sum of
absolute value of differences in the goal between x coordinates and y coordinates. Diagonal
distance means calculate the maximum absolute value of difference in the goal between x
coordinates and y coordinates. The Euclidean distance also calculate the 2D grid world that using
to find the distance between initial state and target state.
Pseudo code
-Initially open the list
-Initially close the list
The starting node on the open
List
-While (open list is empty)
a) The open list is q and find the node with start
b) Pop q off the open list
c) Generate the q successor’s node
d)Successors node
a)If(goal=success)
Successor=q.d+ distance between successor and q

Successor. e=Distance form goal to successor
Successor. f=successor. d +successor. e
b)If the node execute the same position then the open list
end
e) Close the list
end (while loop)
Algorithm for Minesweeper problem and Whale watching problem
Algorithm for Minesweeper problem
Consider the minesweeper grid value that contains the at least one correspondence
between the each grid value (DelMarco, 2014). It is two dimensional grid of black squares which
used to find the distance between the two states.
Algorithms
1. The ells are randomly assigns.
2. Calculate the neighbour mine count for each cell
3. In right cell
a)IF the cell is opened is true then do nothing
b)If the cells is opened is false then it show the flag
4. In left cell
a)If the cell is opened is true then do nothing
b)If the cell is opened is false then the execute is over
5. Multi Click
If the cell neighbour mine count is 0 then do nothing
If the cell neighbour mine count is greater than 0 then it show the flag.
Algorithm for Whale watching problem
Consist the 10x10 array gird world and it contains the numbered between from 0 to 9
inclusive (Malakar and Hanrahan, 2015). We have apply the distance measurement formula for
update the Bayesian and show that ship model value. To implement the whale watching scenario
suing the run function.
1. It start with the initial state and that has the maximum number of iterations.
2. To initialize the initial values.

3. Generate the values randomly then search the value.
4. Assign the best search agent.
5. The step repeated until the termination.
a) The value increased when increase iteration count.
b) The parameter are updated for each value.
c) To using the exploration approach for this iteration.
d) Finally produce the best found search agent.
Conclusion
In this project successfully implement the decanting problem and Bayesian update
problem using python code. The search algorithm apply for find the value. It has the initial value
and target value. That value is consider for find the distance between x coordinates value and y
coordinates value. First task is to solve the decanting problem form given data and process the
value using python code. In second task to simulate a ship trying a whale grid in a 10x10 grid
world using python code. It has the 10 x10 array gird world both x and y coordinate are numbers
from 0 to 9 inclusive. We have apply the distance measurement formula for update the Bayesian
and show that ship model value. Finally successfully implement the decanting problem and
Bayesian update for whale watching scenario using python code.

References
Chlond, M. (2011). Puzzle: Minesweeper Puzzles. INFORMS Transactions on Education, 11(2),
pp.90-91.
DelMarco, S. (2014). Search algorithm cost modeling offers search efficiency measures. SPIE
Newsroom.
Hacker Noon. (2019). Search Algorithms in Artificial Intelligence. [online] Available at:
https://hackernoon.com/search-algorithms-in-artificial-intelligence-8d32c12f6bea [Accessed
28 Apr. 2019].
Malakar, C. and Hanrahan, M. (2015). Whale watching. Reservoir, Vic.: Preston Reservoir Adult
Community Education.