Warning

# Searching a State Space – Informed Search

A Guide for the Seminar

Authors: Milan Rollo, Eduard Semsch, Štěpán Urban, Viliam Lisý a Petr Benda
Edit: Tibor Strašrybka

### Goals

Practice the informed state-space search solutions. It is important for students to understand the UCS algorithm, the greedy algorithm and the A* algorithm and that they are capable of discussing their features and limitations. The seminar plan is:

• An informed state-space search
• A search based on the price so far – map being an example. Uniform Cost Search (f = g)
• A search according to the future price, greedy – map. (f = h)
• A, A* as a combination of the above mentioned – map. (f = g + h)
• Practical discussion about the features of A*

## Examples

### A maze

You are given a map of the maze. Black squares are inaccessible. Cost of passing through grey squares is 3, while cost of passing through white is 1. The task is to plan a path from square A to square B (or C) with a smallest cost.

#### 1) Uniform cost search algorithm (UCS)

Use the UCS algorithm to find a path from square A to square B. Is the solution going to be optimal?

#### 2) Greedy Best-First Search algorithm

Apply the best-first search algorithm. Use the distance to the target expressed as the taxicab (Manhattan) norm (sum of the absolute differences in coordinates also known as Manhattan distance). If there are multiple squares within the same distance, white squares are preferred, if there are still more than more square, pick at random.

The task is identical to the previous one. The only difference is the algorithm to be used.

#### 3) A, A* algorithm

Apply the A algorithm. The heuristic function is the taxicab norm again.

The task is identical to the previous ones. Compare the number of steps and optimality of solutions given by these three algorithms we have shown.

### Production scheduling

A factory needs to plan (schedule) the production of 50 types of products on the manufacturing line. The constraints are the capacity of the line in units/hour and for each of the product types and shipping orders for units of a product type (hundreds of orders). The profit (optimality) is given by uniformity of the line load (price of overtimes and pauses) and storing price for each of the early manufactures products per day.

For practical reasons (machine setup) it is important to keep manufacturing continuously a single product for as long possible. The storage is empty at the beginning.

Propose a formal description of the task, describe the state-space and constrains, design a heuristic and discuss the features of the A* algorithm.

### Example of a Heuristic

Airplane: The airplane may fly in one of the four flight altitudes. The fuel consumption in the first one is 5 units of fuel per a unit of distance. The second one has 4 units etc. The fuel consumption during transition between levels is 10, when going up, 1 when down. The airplane has to travel between airports 10 units of distance far from each other. The plane’s fuel capacity is 50 units of fuel. Optimize the fuel consumption.