# Exercises for Chapter One: Problems

1.  Consider the well-known graph k-colouring problem. Here we are given a set of points (vertices) and a list of connections between them (edges). The task is to assign one of k colours to each vertex, so that no two vertices which are connected by an edge share the same colour.
1. Formalise this problem as a free optimisation problem.
2. Formalise this problem as a constraint satisfaction problem.
3. Formalise this problem as a constrained optimisation problem.
2. A group of students are tasked with building a robotic system to play table tennis. For each of the following capabilities that the system should exhibit, state whether it is an optimisation, modelling, or simulation problem.
1. Identifying the ball in a video feed.
2. Predicting where the ball will bounce.
3. Planning how to move the bat to the predicted position of the ball at some future time.
4. Learning opponent’s behaviour.
5. Deciding where to hit ball next so that the opponent has the smallest chance of returning it.
3. A company decides to produce a robotic system that can guide groups of potential students and their parents around a university campus on an open day. There are considerable regional differences in dialects across its target markets. For each of the following capabilities that the system should exhibit, state whether they are an optimisation, modelling, or simulation problem.
1. Learning to recognize speech.
2. Recognizing a question.
3. Planning a route to the next room on the tour.
4. Recognizing an obstacle in a corridor (it gives a bad impression to run people over).
5. Moving to avoid an obstacle.
4. There is much current research in producing autonomous vehicles that can be used on real roads. For each of the following capabilities that such a system should exhibit, state whether they are an optimisation, modelling, or simulation problem.
1. Learning to recognize traffic signs.
2. Recognizing a traffic sign in a video feed as the vehicle drives along.
3. Planning shortest, or quickest, route between two places.
4. Avoiding a child that runs into the road.
5. Steering in the middle of the road.