\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{ulem}
\usepackage{framed}
\begin{document}
\title{CS 4804 Homework 1}
\author{}
\date{}
\maketitle
Homework must be submitted electronically following the instructions on the course homepage. For some problems, I'm including a sample answer that you can use to gauge what level of detail I'm expecting.
\section*{Written Problems}
\begin{enumerate}
\item (based on R+N Problem 2.4) For each of the following activities, give a PEAS description of the task environment and characterize it in terms of the properties listed in Section 2.3.2. You will be explicitly graded on whether you provide a reasonable comment on the environment's \textbf{performance measure}, its \textbf{environment}, its \textbf{actuators}, its \textbf{sensors}, its \textbf{observability}, whether it is \textbf{single-agent or multi-agent}, \textbf{stochastic or deterministic}, \textbf{episodic or sequential}, \textbf{dynamic or static}, and \textbf{continuous or discrete}.
\begin{itemize}
\item Playing soccer.
\begin{framed}
\textbf{Sample answer:} (I assume Russell and Norvig were asking about robot soccer, but I'm answering for the scenario where we want AIs to compete in human soccer.)
The \textbf{performance measure} should mostly weight whether the team wins the match, but it should also include secondary goals, such as having more shots on goal, longer time of possession, fewer turnovers, etc.
The \textbf{environment}, assuming this is playing soccer on a human-sized field, is a soccer field, with either natural or artificial grass.
For the \textbf{actuators}, again assuming a full-sized soccer setting, to make the game follow the rules of human soccer, we would have to have bipedal robots whose feet are used to move the robot around as well as to manipulate the ball by dribbling, shooting, or passing. The robots should also have hands for throwing and a ``head'' for heading the ball.
For \textbf{sensors}, I'd imagine they would have cameras for eyes if we want to make it especially challenging for the AIs, or if we want to make it easier, they could have radar and LIDAR to obtain a high quality 3D data about the environment.
Soccer is partially \textbf{observable}, cooperatively \textbf{multi-agent} (but competitive against the other team, which may or may not be run by AI), and \textbf{stochastic}. It's \textbf{episodic} between matches, but within each match, it's \textbf{sequential}. It's very \textbf{dynamic}, since it's a fast-moving sport, and it's \textbf{continuous}.
\end{framed}
\end{itemize}
\begin{enumerate}
\item (2.5 points) Shopping for used AI books on the Internet.
\item (2.5 points) Knitting a sweater.
\end{enumerate}
\item (based on R+N Problem 3.6) Given a complete problem formulation for each of the following. Choose a formulation that is precise enough to be implemented. You will be explicitly graded on whether you include discussion of the \textbf{states}, including the \textbf{initial state} if relevant, \textbf{actions}, \textbf{transitions} between states, \textbf{goal test} or success conditions, and \textbf{path costs} unless it is very obvious that the path costs are all the same.
\begin{itemize}
\item Using only four colors, you have to color a planar map in such a way that no two adjacent regions have the same color.
\begin{framed}
\textbf{Sample answer: } Each \textbf{state} is a complete coloring of the map. The \textbf{goal states} are any colorings that satisfy the adjacency requirement. If we knew what these states were, we'd be done, so in this problem, we won't have explicitly encoded all the states. Instead, we'll just have a \textbf{goal-test function} that checks if any adjacent regions are the same color and if so returns false. The \textbf{actions} between states will be any change to the color of any one region. This means if there are $N$ regions, each state will have $3N$ actions out of the state (recoloring a region with its current color would have no effect). The \textbf{transitions} are then between fully colored maps, changing the color of one country at a time. The \textbf{initial state} could be a random coloring, and we would then search from there.
\end{framed}
\end{itemize}
\begin{enumerate}
\item (2.5 points) You have a program that outputs the message ``illegal input record'' when fed a certain file of input records. You know that processing of each record is independent of the other records. You want to discover what record is illegal.
\item (2.5 points) You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.
\end{enumerate}
%\pagebreak
\item (R+N Problem 3.21) Prove each of the following statements (this can be done in English without complex math), or give a counterexample if it is false:
\begin{enumerate}
\item (2 points) Breadth-first search is a special case of uniform-cost search.
\item (1 point) Depth-first search is a special case of best-first tree search.
\item (2 points) Uniform-cost search is a special case of A* search.
\end{enumerate}
\end{enumerate}
\end{document}