We consider the following Analogy problem (taken from Evan's paper). As indicated by the figure, the idea is to find the figure among 1 to 5 which to (c) what (b) is to (a) (the example is taken from the 1942 edition of the Psychological Test for College Freshmen of the American Council on Education)
Write a short python code to solve this problem. We will store the objects as dictionnary with the following fields: a name (unique identifier for each figure, you can choose it), a shape (for the moment, triangle, square and disk or circle), a size (we will consider three sizes : small, medium or large) we will add three more descriptive fields :
We will store each image as a list of the figures it contains.
(here we will manually encode the representation although as indicated in the paper of Evans, the translation from the image through its list representation could easily be implemented by a simple scanner)
For this, the idea is to implement a diagram similar to the one shown below. We decompose each figure into its objects. We then study how those objects change from (a) to (b) and apply the corresponding transformations to each of the object from the second image. Then compare with the figures 1 to 5 (following the idea of the diagram below) in order to find the matching figure.
Start by drawing the diagram (with pen and paper) relating (a) to (b) as shown below. Then apply the corresponding transformations to the new figure.
Note that although you can start by assuming no scaling for simplicity, from (a) --> (b) it is a priori not clear whether it is the larger triangle which was retained or if it is the smaller one that was scaled up after deleting the small one. Ultimately your code should take the possibilities into account (i.e. this will actually be needed in I.3).
Apply your algorithm to solve the following Analogy problem
Apply your algorithm to solve the following Analogy problem
Refine your pipeline so that it can handle the ambiguous Analogy below.
Refine the solution you provided for the previous exercises in order to solve the new analogy below.
We now consider a more ambiguous problem where there is no direct matching in the sense described above. The example is again taken from Evan's seminal paper on ANALOGY.
Hint: Start by trying the above/below relations encoded in the transformation between figure (a) and (b). if you can't get any match, one appoach consists in substituting one transformation for another (e.g. after checking that the original relation (above-below or vertical swap) cannot be applied, one can for example check the substitution of the vertical transformation for an horizontal one.)
We consider the vacuum cleaner world shown below. This world can be characterized as follows:
The state of the environment is defined jointly by both the vacuum cleaner location and the dirt location. I.e. the agent is in either of two locations, each of which might contain dirt. In total there are thus $2\times 2^2 = 8$ (i.e. the vacuum cleaner can be in either of the two cells (exclusively) and there can be dirt everywhere) possible world states.
In this environment, each state has 3 associated actions: Left, Right and Suck (Larger envinronement will include the additional Up and Down moves)
Any state can be defined as the initial state
The actions have their respective effects except moving left in the leftmost square and moving right in the rightmost square
The objective of the vacuum cleaner is for all the cells to be clean
In this framework, we will consider that each step costs 1 so the total cost of a path is the number of steps in the path.
Implement a performance measure environment simulator for the vacuum cleaner world. Your environment should be modular so that the sensors actuators and environment characteristics (size, shape, dirt placement can be changed easily)
Implement a simple reflex agent for the environment you just defined. Run the environment with this agent for all possible initial dirt configurations and agent locations. Record the performance score for each configuration and the overall average score.
Consider a modified version of the vacuum environment in which geography of the environment (its extent, boundaries and obstacles) is unknown, as is the initial dirt configuration. (The agent can now go Up and Down as well as Left and Right)
Extend the environments from above to the following stochastic frameworks:
In this third part, we will review the basic search algorithms and implement simple search agents. When trying to solve a general problem, the simplest approach is to discretize the space into the complete set of candidate solutions (which can be extremely greedy) and explore this space, through search algorithms to find an optimal solution (examples of applications involve route finding, equation solving, ...).
In this first question, we will review basic search algorithms
There are several approaches at building trees in Python. The most common approach is to define the tree as a separate data structure (through a Node type for example). See below.
class Node(object):
def __init__(self, data): # initialize the node without children
self._data = data
self._children = []
def getChildren(self):
return self._children
def getData(self):
return self._data
def addChild(self, child):
self._children = self._children.append(child)
Using the code above, store the tree given below as a tree object using the node class (or any other efficient approach you like).
Note : you can tag the nodes as you like
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
A = nx.random_tree(20)
nx.draw(A)
Once you have built the tree, explore this tree with
and display the sequence of nodes.
Apply your Search agent to compute an optimal sequence of actions in a $3\times 3$ world whose initial state has has dirt in the three top cells and the agent is in the center of the $3\times 3$ grid.
Evaluate the performance of your agent by generating a set of $3\times 3$ worlds with probability $0.2$ of dirt in each cell. Compare the efficiency of your agent with a simple randomized reflex agent that would suck where there is dirt and otherwise move randomly.
The Missionaries and cannibals problem can be stated as follows. Three missionaries and three cannibals are on one side of a river along with one 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. The problem is famous in AI because it was the subject of a first paper that approached problem formulation from an analytical viewpoint (Amarel 1968)
Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.
Implement and solve the problem optimally using an appropriate search algorithm.
We consider the problem of finding the shortest path between between two points on a plane that has convex polygonal obstacles as show below. This can be considered as an idealization of the problem that a robot has to solve to navigate in a crowded environment.
A efficient approach in such an environment is to consider the straight line between the vertices of any two shapes to be the shortest path between those vertices. Using this idea, how would you define the sate space? How large is that space?
Define the necessary functions to implement the search problem, including an action function that takes a vertex as input and returns a set of vectors, each of which maps the current vertex to one of the vertices that can be reached in a straight line (do not forget th neighbors on the same polygon). You can use the straight line distance as your heuristic function.
Apply one or more of the search algorithms covered during the lectures and comment on their performance.
Consider the 8 puzzle below.
This puzzle consists of a $3\times 3$ board with $8$ numbered tiles and a blank space. A tile adjacent to the space can slide into the blank space. The objective is to reach a specific goal state such as the one shown on the right. Concretely in the $8$ puzzle,
Try to solve this problem with $A^*$ first and RBFS. Use as your heuristics
Compare the performance of RBFS and $A^*$ for those two heuristics.
In the exercise above, we considered two simple heuristics: the Manhattan distance and the misplaced tiles. Several other heuristics have been introduced in the litterature to improve the resolution of the puzzle. Check Nilson (1971), Mostow and Prieditis (1989) as well as Hansson et al. (1989). Test the conresponding heuristics and compare them to the results you get from the Manhattan and misplaced tiles approaches.