Introduction to AI

Module 5: Planning and multi-agent systems

Summary

  • Topics: This module will cover the following topics.
    • Knowledge representation: how do we represent knowledge in a form that can be communicated clearly among multiple agents?
    • Classical planning:  How classical planning methods work and how we can use them to achieve goals
    • Multi-agent systems: How can we combine effective knowledge representation with planning to create a team of agents working together to achieve a goal?
  • Length: This module will take two weeks to complete
  • Assigned chapters: Parts of Chapter 7, 11, 18
  • Project: Project 4 (will stay open two weeks beyond this module)

Planning & multi-agent syStems

This module is going to cover several topics in one because they are interrelated.  It is entirely possible to make an entire class on multi-agent systems, and indeed, one may exist at OU in the near future with our new faculty!  However, this class focuses on an overview of AI and, as such, we cannot spend the entire semester on one topic. 

For this module, we will start with a discussion of how to represent knowledge in a logical manner.  This will enable the agents to share their information about their current internal state as well as any knowledge about the environment they have gathered.  By using a logical representation, the knowledge is shared in a consistent and clear manner.  Note that we are not going to require propositional logic, we just approach the knowledge representation from this angle and then relax the representation as much as possible while maintaining the ability to do joint planning.

We will move from knowledge representation to planning, which is the reason for the fun picture of Shakey the robot.  Shakey’s creators were involved in the original development of classical planning approaches, which we will discuss as part of learning about planning.

Finally, we will tie the two topics together and discuss how we can use the logic-based knowledge representation together with planning to enable multiple agents to accomplish goals together.

Shakey the Robot

Shakey the robot

This image is from the writeup about Shakey the robot

Assignments for Module 5

Topic 1: logical agents and knowledge representation

We will begin this module with a discussion of logic and various ways to represent the knowledge of an agent.  It is important that we represent knowledge in a manner that facilitates communication between agents.

  • (30 min) Reading
    • Read Sections 7.1-7.4 of Chapter 7 (Introduction through Propositional logic)
    • If you need a review on logic and knowledge representations, there is a great overview in chapters 7, 8 and 10. Because most CS students have a thorough background in logic, I am not requiring you to read these but I highly recommend them if you feel like you need a review or to catch up!
  • (60 min) Knowledge representation 
    • Watch the video on why are we discussing multi-agent system, planning, and knowledge representations
    • Watch the video on how to represent information about the environment from different points of view
    • Watch the video with an example of the knowledge engineering process using Wumpus world
    •  Consider the Monkey and Bananas problem shown on the last slide and described here, in slack discuss what you think an appropriate vocabulary for this problem is.  You need to read your fellow student’s answers and actually discuss, not just post and not read.  Discuss this on #general

 

Topic 2: Planning

Once we understand how to represent knowledge in the agent, we will discuss planning.  This first part of the discussion does not discuss multiple agents, only the classical planning methods.  The next topic will tie in the multiple-agents.

  • (30 min) Reading
    • Read Sections 11.1-11.2 of Chapter 11 (Introduction through Algorithms for Classic Planning)
  • (60 min) Planning
    • Watch the video on how to setup a planning problem including how to represent states, goals, and action schemas 
    • Example of how to setup for planning
    • Forward search
    • Backward search
    •  Complete the exercise on planning, schemas, and search

 

Topic 3: Planning in the real-world (including multi-agent systems)

Our final topic in this module focuses on how to extend the planning methods to real-world situations, including multi-agent systems and dynamic stochastic environments.

  • (30 min) Reading
    • Read Section 18.1 

project for module 5

Project 3

  • Project 3 due (on adversarial search) is due midway through this module – Sun Oct 10.  

Project 4

  • Project 4 is assigned during this module because it focuses on multi-agent systems.  Knowing that you are still completing projects from the previous modules, you do not start this until partway through the module (week 2).  This is one of the harder projects so make sure you start it during this module and please be sure to ask questions in #projects about it!

suggested schedule for module 5

Week 1 (Oct 3-10)

  • Complete Topic 1 by Wednesday
  • Work on Project 3 all week and aim to have it partially working by Wednesday
  • Complete Topic 2 by Saturday
  • Complete Project 3 by Sunday Oct 10

Week 2 (Oct 10-17)

  • Read Project 4
  • Complete Topic 3 by Wednesday
  • Work on Project 4 all week with the goal of a partially working system by Sunday

Week 3 (Oct 17-24)

  • Work on Project 4 (you will be in the next module for content)

Week 4 (Oct 24-31)

  • Project 4 is due (you will be in another module here, I’m trying to give you enough time to fully work on project 4 since it is one of the larger ones.)