Assignment 1 Solution

Description

Please submit the solution to each problem on Canvas. Submit only one text or word file. Clearly mark the answer to each problem.

1. (5 points) You get the full points if either

1. • all the rest of the assignment elements work or

1. • 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

2. 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.

Assignment 1 CSCI 440 Artificial Intelligence Fall 2019

3. (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);