Home / Research / Books / MAS: Algorithmic, Game-Theoretic, and Logical Foundations

MAS: Algorithmic, Game-Theoretic, and Logical Foundations

Title: MultiAgent Systems: Algorithmic, Game-Theoretic, and Logical Foundations
Authors: Yoav Shoham and Kevin Leyton-Brown

Chapter 1 and 2 Distributed problem solving.
Chapters 3, 5 and 6 constitute a crash course in noncooperative game theory
Chapter 7 Learning
Chapter 8 Communication
Chapter 13 we cover modal logic of knowledge and belief.
Chapter 14 we discuss how beliefs change over time, and how one might begin to use logic to model motivational attitudes in addition to the informational ones (knowledge, belief).
Ch1. Distributed Constraint Satisfaction
– A constraint satisfaction problem (CSP) is defined by a set of variables, domains for each of the variables, and constraints on the values that the variables might take on simultaneously. The role of constraint satisfaction algorithms is to assign values to the variables in a way that is consistent with all the constraints, or to determine that no such assignment exists.
– The essence of this problem can be captured as a graph-coloring problem.
– The goal of graph coloring is to choose one color for each node so that no two adjacent nodes have the same color.
– A distributed algorithm for solving a CSP has each agent engage in some protocol that combines local computation with communication with his neighbors
– We discuss two types of algorithms. Algorithms of the first kind embody a leastcommitment approach and attempt to rule out impossible variable values without losing any possible solutions. Algorithms of the second kind embody a more adventurous spirit and select tentative variable values, backtracking when those choices prove unsuccessful.
– 1.2 Domain-pruning algorithms
– The asynchronous backtracking (ABT) algorithm assumes a total ordering (the “priority order”) on the agents.
Ch2. Distributed Optimization
2.1 Distributed dynamic programming for path planning
– Like graph coloring, path planning constitutes another common abstract problemsolving framework. A path-planning problemconsists of a weighted directed graph …
– divide-and-conquer procedure, also known as dynamic programming
– In the learning real-time A∗, or LRTA∗, algorithm, the agent starts at a given node, performs an operation similar to that of asynchronous dynamic programming, and then moves to the neighboring node with the shortest estimated distance to the goal, and repeats.

About Mohammad Khazab

Leave a Reply

%d bloggers like this: