Give a complete problem formulation for each of the following.

You have to color a planar map using only four colors, in such a way that no two adjacent regions have the same color.

A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He would like to get the bananas. The room contains two stackable, movable, climable 3-foot- high crates.

## EXPERT ANSWER

- Initial state: Assign a color to an uncolored region.

Transition model :The uncolored region has the assigned color.

Goal test: All regions colored, and no two adjacent regions have the same color. Cost function: Number of assignments. - Initial state: 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling.

Transition model: Hop on,off crate; Push crate,Stack from one spot to another; Walk from one spot to another; Grab bananas (if standing on crate).

Goal test: Monkey has bananas.

Cost function: Number of actions.