# Search

## Changes from e42e193aead27f11df40a7ed818f547d881ea102 to 6a6bdf3ce47fed44dde15960e5ea018f9754374f

---
title: Search
categorie: session
---

R&N Chapter 3.1-3.4.

# Briefing

+ Problem Solving Agent vs Planning Agent
- problem solving agent -> atomic representation
+ Goal -> Problem -> Search -> Execution
+ Modelling: State Machine
- Steates - Transitions; Intial State - Goal; Actions - Action Cost
+ Informed:
-  Best-First Search
-  Redundant Paths
- Performance
+ Uninformed: Tree Searchs
- Depth First
- Bidirectional Search

# Group Work Exercises

This exercises are taken from the
[AIMA Exercises](https://aimacode.github.io/aima-exercises/search-exercises/).

## 2.4

For each of the following assertions, say whether it is true or false and

1. An agent that senses only partial information about the state cannot
be perfectly rational.
2. There exist task environments in which no pure reflex agent can behave
rationally.
3. There exists a task environment in which every agent is rational.
4. The input to an agent program is the same as the input to the agent
function.
5. Every agent function is implementable by some program/machine
combination.
6. Suppose an agent selects its action uniformly at random from the set
of possible actions. There exists a deterministic task environment in
which this agent is rational.
7. It is possible for a given agent to be perfectly rational in two
8. Every agent is rational in an unobservable environment.
9. A perfectly rational poker-playing agent never loses.

## 3.2

Give a complete problem formulation for each of the following problems.
Choose a formulation that is precise enough to be implemented.

1. There are six glass boxes in a row, each with a lock. Each of the
first five boxes holds a key unlocking the next box in line; the last box
holds a banana. You have the key to the first box, and you want the
banana.
2. You start with the sequence ABABAECCEC, or in general any sequence
made from A, B, C, and E. You can transform this sequence using the
following equalities: AC = E, AB = BC, BB = E, and Ex = x for any x. For
example, ABBC can be transformed into AEC, and then AC, and then E. Your
goal is to produce the sequence E.
3. There is an n×n grid of squares, each square initially being either
unpainted floor or a bottomless pit. You start standing on an unpainted
floor square, and can either paint the square under you or move onto an
adjacent unpainted floor square. You want the whole floor painted.
4. A container ship is in port, loaded high with containers. There 13
rows of containers, each 13 containers wide and 5 containers tall. You
control a crane that can move to any location above the ship, pick up the
container under it, and move it onto the dock. You want the ship unloaded.

## 3.5

Suppose two friends live in different cities on a map, such as the
Romania map shown in . On every turn, we can simultaneously move each
friend to a neighboring city on the map. The amount of time needed to
move from city i to neighbor j is equal to the road distance d(i,j)
between the cities, but on each turn the friend that arrives first must
wait until the other one arrives (and calls the first on his/her cell
phone) before the next turn can begin. We want the two friends to meet as
quickly as possible.

1. Write a detailed formulation for this search problem. (You will find
it helpful to define some formal notation here.)
2. Let D(i,j) be the straight-line distance between cities i and j. Which
of the following heuristic functions are admissible? (i) D(i,j); (ii)
2⋅D(i,j); (iii) D(i,j)/2.
2. Let $D(i,j)$ be the straight-line distance between cities $i$ and $j$. Which
of the following heuristic functions are admissible? (i) $D(i,j)$; (ii)
$2\cdot D(i,j)$; (iii) $D(i,j)/2$.
3. Are there completely connected maps for which no solution exists?
4. Are there maps in which all solutions require one friend to visit the
same city twice?

## Blunder at CodinGame

+ [Blunder Episode 2](https://www.codingame.com/training/hard/blunder-episode-2)

This is rated as **hard**, but given that you study AI and this week,
we discuss **search trees**, it should not be too hard.

Team up and discuss how this game can be modelled as a tree and how
you can traverse it to maximise Blunder's loot.

# CodinGame challenges

## Medium Problems

1.  [Don't Panic --- Episode 1](https://www.codingame.com/training/medium/don't-panic-episode-1) (conditions)
+ You need to help Marvin and his clones (or is it the other way round?) reach the exit in order to help them escape the inside of the Infinite Improbability Drive.
+ *Also given in Week 2*
+ Batman will look for the hostages on a given building by
jumping from one window to another using his grapnel gun.
are located in order to disarm the bombs.
Unfortunately he has a limited number of jumps before the bombs go off
...
4.  [Death First Search - E1](https://www.codingame.com/ide/puzzle/skynet-revolution-episode-1)
+ You need to assess the opponent's possibilities, keeping track
of multiple possibilities.
3.  [Mars Lander --- Episode 2](https://www.codingame.com/training/medium/mars-lander-episode-2) (distances, trigonometry)
+ The goal for your program is to safely land the *Mars Lander* shuttle,
the landing ship which contains the Opportunity rover.
Mars Lander is guided by a program, and right now the failure
rate for landing on the NASA simulator is unacceptable.
This puzzle is the second level of the *Mars Lander* trilogy.
The controls are the same as the previous level but you must now control the angle in order to succeed.

## Harder Problems

1.  [Don't Panic --- Episode 2](https://www.codingame.com/training/medium/don't-panic-episode-2) (conditions)
+ Hard.  Builds on the previous episode above.
4. [Death First Search - E2](https://www.codingame.com/ide/puzzle/skynet-revolution-episode-2)
+ Hard.  Builds on the previous episode above.
3.  [Mars Lander --- Episode 3](https://www.codingame.com/training/expert/mars-lander-episode-3) (distances, trigonometry)
+ Very hard.  Builds on the previous episode above.