Description
Please submit the solution to each problem on Canvas. Submit only one text or word file. Clearly mark the answer to each problem.
-
(5 points) You get the full points if either
-
-
all the rest of the assignment elements work or
-
-
-
you spend a considerable amount of time working on trying to get the assignment working o Record the approximate amount of time working on the assignment
-
o Detail the parts you struggled with and your attempts to get them working
-
Modified book Problem 3.9. The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).
An implementation of the node structure is given to you.
struct mcNode {
//structure of each node in the tree
int state;
//state of the node
-
x =1 if boat is on the original side of the river, x=0 otherwise
-
y = “number of missionaries on the original side of the river”
-
z = “number of cannibals on the original side of the river” //state=x*100+y*10+z
int parent; //the state of the parent node
double costG; //g(n), cost (1 per step) from start to present
int action; //1=one cannibal on the boat; 2=two cannibals; 10=one missionary; 20=two
missionaries; 11=one missionary+one cannibal
};
-
(2 points) Implement a function that given a current node, will create and return all the successor nodes as a vector of mcNode.
vector<mcNode> getSuccesors(mcNode curr);
-
(1 point) The problem has no solution if there are 4 couples (4 missionaries and 4 cannibals). However if the boat capacity is increased to 3, then solutions to 4 and even 5 couples (5 missionaries and 5 cannibals) exist. Implement the getSuccessors function for boat capacity 3 and up to 5 couples.
vector<mcNode> getSuccesors35(mcNode curr);
Assignment 1 CSCI 440 Artificial Intelligence Fall 2019
-
(2 points) Modified book Problem 3.7. Consider the problem of finding the shortest path between two points on a plane that has convex polygonal obstacles as shown in Figure below. This is an idealization of the problem that a robot has to solve to navigate in a crowded environment.
G
S
A scene with polygonal obstacles. S and G are the start and goal states.
The shortest path from one polygon vertex to any other in the scene must consist of straight-line segments joining some of the vertices of the polygons. You are given a file representing a graph. The vertices of the graph are the vertices of the polygons and the starting and goal positions. The edges of the graph are all the above pairs of vertices that can be connected by a straight line without going through an obstacle. An implementation of the node structure and the graph structure is given to you, as well as a function that populates the graph from the data file. Implement a function that given a current node, will create and return all the successor nodes as a vector of nodeType. The costG of the new node is the costG of the parent + the distance from parent to child. For now, set costH of the new node to 0.
vector<nodeType> getSuccesors(nodeType curr, navigationGraph g1);
