Multiagent Search
Welcome to Lecture 4 – Multiagent Search! Here we go a step back to our search problems and ask ourselves what happens if I’m not alone making decisions. Up until now we only considered scenarios where our agent was the only one making decisions and nothing could stop us executing the actions as planned. Now we have a second agent, this agent might have a different goal, it might even have the opposite goal of ours or might just act randomly. In any case, we need to take that into account as this agent’s actions and decisions influences the decisions and actions we can make. This is not just relevant for playing games – even though playing games is often used to track the progress of technologies – but also for acting in the real world, when the agent needs to work together with humans, look out for other road users and so on. We will learn how to account for an adversarial agent using Minimax or for a random agent using Expectimax. In the last parts of the lecture, we will look at how to model agents’ preferences using utilities and what the utilities of humans are.
Topics in this course:
- Games (MultiAgents 1)
- Minimax and it’s improvement Alpha-Beta Pruning (MultiAgents 2 and 3)
- Evaluation Functions (MultiAgents 4)
- Expectimax and Probabilities (MultiAgents 5 and 6)
- Modelling (MultiAgents 7)
- Utilities (MultiAgents 8 and 9)
The lecture videos can be found here.
Step-by-step examples and additional explanations:
- Minimax and Alpha-Beta Pruning
- Expectimax
- Lotteries and Utilities