Introduction to Artificial Intelligence Assignment  

PROBLEM 1 - INFORMED SEARCH

The Pancake Problem

A messy cook has a disordered stack of 5 differently-sized pancakes [size from 1 to 5] and a spatula that can be inserted at any point in the stack and used to flip all pancakes above it. The goal is for the cook to have them in the "correct" order for the customer, that is, the large on the bottom up to the smallest on top ([5, 4, 3, 2, 1]).

1. Define the problem as a searching problem

2. Define a possible cost function (backward cost)

3. Define a possible heuristic function (forward cost)

4. Implement an A* algorithm in your language of preference

BONUS - Could the Dijkstra's algorithm be used? If so, provide an implementation of the same Pancake Problem with Dijkstra.

PROBLEM 2 - BEHAVIOR TREES

Roomba's roaming

This new type of Roomba has very simple reflex rules. It will always check the battery level first. If the level is below 30%, it will plan a path to its charging base ("home"), go there, and start the docking procedure. If the battery is at a sufficient level, it will start the function it was commanded to perform. The available commands are:

1. Spot cleaning: it will perform a 20s intensive cleaning in a specific area

2. General cleaning: go around the room and vacuum dust until the battery falls under 30%

3. Do nothing

During general cleaning, if the dust sensor detects a particularly dirty spot, the Roomba will perform a 35s spot cleaning.

The goal of this problem set is to implement the provided behavior tree. As we talked about in class, trees can be represented with concatenated IF-THEN-ELSE rules. Trees can also be implemented through a standard recursive node definition.

Your implementation should accept a blackboard object as input (a regular hash map or dictionary). The blackboard contains the following elements:

1. BATTERY_LEVEL: an integer number between 0 and 100

2. SPOT: a Boolean value - TRUE if the command was requested, FALSE otherwise

3. GENERAL: a Boolean value - TRUE if the command was requested, FALSE otherwise

4. DUSTY_SPOT: a Boolean value - TRUE if the sensor detected a dusty spot during the cycle, FALSE otherwise

5. HOME_PATH: The path to the docking station

SPOT and GENERAL should not change until the command has been completed. The tree evaluation is called several times, each time simulates a 1s interval. Certain tasks should return RUNNING if they have not completed the job yet, and last for the specified number of cycles (20 cycles, or 35 cycles).

Except for DONE GENERAL and DONE SPOT, none of the other tasks will need to be implemented as printing a string with the name of the task and the state (SUCCEEDED, FAILED, RUNNING) will be sufficient. DONE GENERAL and DONE SPOT will set to FALSE the corresponding values in the blackboard.

SUBMISSION - Submit your solutions via Trunk.