Revision 5b942bb08bee30f9f774e5d99db9b89da12bf290 (click the page title to view the current version)

Rational Agents

Preparation

Reading Russel & Norvig Chapter (1-)2

Learning outcomes

After the completion of this workshop, students should

  • be familiar with CodinGame and have successfully solved some of the recommended Medium puzzles.
  • be able to analyse problems with respect to PEAS (performance measure, environment, actuator, sensor).
  • understand and be able to explain what kind of agent they have implemented (e.g., reflex agent, planning agent, etc.) and whether their agents (or more generally, solution methods) are rational.
  • be familiar on an introductory level with basic data structures and algorithms (e.g., lists, sets, trees, binary search, greedy search).
  • be able to understand and answer the sample exam questions posted on Blackboard that relate to the material covered in this workshop.

Briefing

Recap from last week

We discuss the content from R&N Ch. 1 and the material studied last week. Two questions, state the most important point only:

  1. What have you learnt so far?
  2. What is your greatest challenge for today?

Keywords from last week

  • four definitions of AI along the axes of thinking and acting humanly and rationally.
  • foundations of AI, e.g., philosophy, mathematics, economics, neuroscience, psychology, computer engineering, control theory and cybernetics, linguistics
  • the history of AI
  • applications of AI and state-of-the-art

We divide the class into four groups for each of the talking points. You can use OneNote to enter some notes from your brainstorming. Finally, each group present briefly their topic before a short discussion and comments from the class and teacher.

Review of the reading assignment

Agent is the perceive-think-act cycle
Agent is the perceive-think-act cycle

We divide the group in three groups, to discuss each of the following topics from the reading assignments. Each topic should be discussed using the coding problems from last week as examples.

  1. PEAS - Performace Measure, Environment, Actuators, Sensors
  2. Properties of the task environment
    • Fully or partially observable
    • Single or multi-agent
    • Deterministic or not
    • Episodic or sequential
    • Static or dynamic
    • Discrete or continuous
    • Known or unknown
  3. Program Type
    • simple reflex agent
    • model-based agents
    • goal-based agents
    • utility-based agents
    • learning agents

Lecture

See Lecture on Rational Agents

Discussion

We discuss the content presented by R&N Ch. 2.

  • definition of agent
  • percept and percept sequence
  • agent function and agent program
  • rational agents and performance measures
  • omniscience, learning, and autonomy
  • task environments and PEAS
  • properties of task environments
  • table-driven agents
  • simple reflex agents
  • model-based reflex agents
  • goal-based agents
  • utility-based agents
  • learning agents

Working in pairs, each student in a pair will get 10 mins to prepare a talking point from the list, before giving a short oral presentation to the other student, and vice versa. This is called peer-tutoring. Afterwards, we will discuss the exercise and clarify certain topics and questions you might have (if any).

End-of-chapter exercises in AIMA Ch. 2

Working individually or in pairs, students will be assigned an exercise from the end-of-chapter exercises in AIMA Ch. 2. After having worked on the problem for a little, with notetaking in OneNote, the worked solutions will be presented to the rest of the class.

Exercises

We continue solving coding challenges primarily on CodinGame. As we progress, try to draw a connection between the coding challenges and the topics we learn. Some help on particular puzzles is provided in the Forum on Blackboard.

Preliminaries

Note that knowledge about various data structures and trees, in particular, binary search trees, will be useful before implementing algorithms presented in this course. You should explore such functionality in your programming language of choice, e.g., in Java, the Collections Framework includes various useful interfaces and classes, e.g.

  • Set: HashSet, TreeSet, LinkedHashSet
  • List: ArrayList, LinkedList
  • Deque: ArrayDeque, LinkedList
  • Map: HashMap, TreeMap, LinkedHashMap

Challenges

Depending on your background, you may want to use GodinGame to train basic programming and algorithmic skills, or to test the rational agent framework discussed today. The challenges are split in two section below.

It is assumed that everybody solved the Power of Thor last week. The solution we discussed in class may prove to be an important pre-requisite below. Apart from this one, the most important problems from last week have been repeated below.

Intelligent Agents

These challenges fit failry well into the framework of intelligent actions. For each challenge you solve, you should discuss how it the problem and your solution can be classified using the terminology of R&N Ch. 2.

  1. The Descent
    • This was also given in Week 1.
    • Description: The enterprise is in danger: drawn towards the surface of an unknown planet, it is at risk of crashing against towering mountains. Help Kirk and Spock destroy the mountains… Save the enterprise!
    • Topic: Search in an array
  2. Shadows of the Knight Episode 1 (medium): intervals, binary search
    • Intelligent Agent
    • Some similarities with the Þor problem last week, but this time the target location is not precisely known
  3. Mars Lander — Episode 1
    • This was also given in Week 1.
    • Description: You have been promoted to commander of the Mars Lander mission! The goal of the operation is to land an exploration rover on martian ground. Your superiors at NASA expect very much of you for this mission, and you’ll have to prove that you have what it takes to become a great intersideral commander. You will have to land the space ship on mars, making sure that the landing is done smoothly.
    • Topic: Speed regulation
  4. Bender Episode 4
    • This is a challenge. You have to take care to build the model and the search tree.
    • Note that you have to find the entire path in your model, and then execute your program. You cannot use a perception loop to try and err.
    • Work in groups. Discuss the model and make sure you can agree on an understanding.
    • Previous episodes no longer available

Feel free to look for additional challenges to solve.

Algorithmic Challenges

The following challenges are more basic algorithmic problems, which may be usefual to practice programming and problem solving in general. You may las

  • There is no Spoon (medium): lists
    • Search problem
    • Using lists is not the only solution
  • Telephone Numbers (medium): trees, sets
    • Calculation - modelling challenge
    • many solutions - can be simulated
  • Advanced tree (medium): tree
    • Build and print a tree
  • The Gift (medium): greedy algorithms
    • Mathematical problem

Debrief

Module evaluation

  • Status report.
  • Questions and Answers?

Homework

Prepare yourself for the next workshop by doing the following:

  1. Review the reading material for this class.
  2. Do the preparation for the next lecture, on Search.