Multi Agent Coordination Flashcards
Coordination
– managing dependencies between activities, or any decision that uses information concerning
the existencee/decisions/decision making strategies of others and adjusting accordingly (Malone & Craston).
- any decision that uses
information that concerns the existence,
decisions, or decision making strategies of
others. (Stirling)
eg: Internet of Thing, Cloud Computing, Factories (Amazon Warehouse), …
characterise cooperative systems
Cooperative systems can be characterised in terms of their environment, the nature of the entities doing the cooperating, or the type of cooperation itself. ● Type of Environment: ○ Diverse/Not Diverse ○ Predictability ○ Dynamics of change ● Cooperating entities ○ How many are there? ○ How homogenous are they? ○ What are their goals? Are they shared goals? Or does each have their own goal? ● Type of Cooperation: ○ Frequency: one-time cooperation? ○ Patterns of cooperation: ■ Recurrent task? ■ Hierarchical Structure?
Coordination Theory Malone & Crowston
Goals: identifying goals
Activities: Mapping goals to activities (goal decomposition)
Actors: selecting actors; assigning activities to actors
Interdependencies: managing interdependencies
Kinds of interdependencies
Prerequesite: output of one activity is required by the next activity (eg: parts to be delivered). Can order activities and move information from one to the next
Shared resource: resource required by multiple activities (eg: installing parts with a common tool). Can decide how to allocate resource
Simultaneity: Time at which more than one activity must occur (eg: installing 2 things at the same time). Must synchronize activities
coordinate instead of having central control
because:
- Principle of Bounded Rationality (Simon):
· The human mind’s processing capacity is limited
· The amount of information that can be processed by an individual is limited
· The detail of control an individual may wield is limited
- Increasing complexity of computer applications
- Distributed AI perspective: to understand intelligence requires to deal with systems able to interact
appropriately
- Coordination is better than one central point that in case of failure would fuck the whole system up
Simple Models and Mechanisms for coordination
Standard Client-Server Task and Result Sharing Blackboard Model Contract Net Model FAC/C Principle (Functionally Accurate Coopereation)
These were simple models of cooperation, where no advantage in task sharing comes automatically.
Client-Server
· Client: sends requests for operations to another process
· Server: receives requests for operations from another process
· Service: operational subject of request by some client
· Client and server can be dynamically played by processes, where a process may act both as a
client and as a server, and a server may be a client of other servers.
· Pros:
▪ Simple control structure
▪ Simple synchronization
· Cons:
▪ Server can be a bottleneck
▪ Poor failure tolerance
▪ Information used by servers may be out of date (communication delays)
· Can be fixed with server replication, but this requires additional coordination and
synchronisation
Task and Results Sharing
generic cooperation model.
· An example is MapReduce, that breaks an input down by
splitting it, mapping part of the input in the splits, shuffling
the mapped input and finally reducing it to the final result.
· Subtask relations:
▪ Disjoint: A and B not touching
▪ Overlapping: A and B partly the same
▪ Subsuming: B fully in A
▪ Identical: A = B
· Pros:
▪ Each subproblem can be solved with less knowledge
▪ Each subproblem requires less resources
▪ Parallelism and robustness
▪ Use of multiple sources of knowledge and skills
▪ Mutual support through exchange of pre-results
· Cons:
▪ Each advantage requires design efforts on its own
▪ Connection problem: who is responsible for which part of the process?
▪ Lots of questions: who knows what, what are the costs, what are strategies, what is
level of task decomposition?
Blackboard system
shared system where agents have read and/or
write privileges on a board where tasks can be posted. It requires
common memory with read/write control.
· Characteristics:
▪ Every participant reads from and writes on a common
memory area
▪ Participants may read/write independently or in a coordinated way
▪ Address of sender needs not be known
▪ Participants themselves decide on information announcement and information
search and evaluation.
· Pros:
▪ Suited for open applications
▪ Supports variability in expertise
▪ Flexible with respect to data structure
▪ Regionalization/structuring is possible
▪ Suitable for event/data driven applications
▪ Supports incremental generation of solutions
· Cons:
▪ Data structure needs to be fixed
▪ Can be chaotic
▪ Central point
· It is used in a topic wise approach by ROS: Robot Operating System, where nodes can push
messages on a topic through a specific channel, and nodes can subscribe to the channels of
interest
Control Net Protocol
very simple negotiation protocol. How it works:
· A network of nodes (cooperating units acting as managers and contractors) where managers
announce tasks to be done and contractors bid for the right to carry out a task. The
contractor with the best bid is selected by the announcing manager.
· A task announcement has:
▪ Eligibility specification (minimal requirements for contractor)
▪ Task abstraction (short description)
▪ Bid specification (structure and contents)
▪ Expiration date
· Pros:
▪ Flexible and distributed control
▪ Dynamic roles (agent can act as manager and/or contractor)
▪ Middle ground between client-server and blackboard
· Cons:
▪ Many design issues: what tasks should be announced, who should receive a specific
announcement, why should a contractor bid etc
Functionally Accurate Cooperation (FA/C)
guideline for cooperation when the individuals’ local
knowledge is incomplete, uncertain and inconsistent.
· Functionally correct: acceptable and reasonable from a local point of view
· Cooperation: iterative refinement, transformation of local into global correctness
· Requirements, involved parties have to be able to:
▪ Measure and evaluate functional correctness
▪ Detect inconsistencies between its tentative partial results and those received from
others
▪ Integrate into its local database those portions of partial results that are consistent
with its own results
▪ Revise and extend its tentative partial results on the basis of the newly integrated data
Advanced Models and Mechanisms for coordination
Auctioning and Voting
Negotiation
Joint Planning
Commitments and Conventions
Auctions types
Contract Net pushed further
· English Auction: first-price open-cry. One variant is open-exit: no re-entry after declaring to
exit the auction (you can’t bid again if other people start bidding).
▪ Bidder is free to raise his bid for predefined amount
▪ Auction ends when no bidder is willing to raise anymore
▪ Highest bidder wins at the price of his bid
· First-price sealed-bid auction:
▪ Each bidder submits one bid without knowing the others’ bids
▪ Highest bidder wins and pays amount of his bid
· Vickrey auction: second-price sealed-bid auction.
▪ Each bidder submits one bid without knowing the others’ bids
▪ Highest bidder wins but at the price of the second-highest bid
· Dutch auction: descending.
▪ Seller continuously lowers the price
▪ Auction ends when one of the bidders takes the item at the current price
Auction characteristics
- Valuation of goods/services:
• Private value auction: each bidder’s value of the good depend only on their
own preference (i.e. art auction)
• Common-value auction: each bidder’s value entirely depends on other
agent’s values (i.e. fresh food auction)
• Correlated value auction: bidder’s value depends partly on own preferences
and partly on others’ values. - Risk attitude:
• Risk-averse bidder: prefers to get the good even if they pay slightly more than private value
• Risk-averse auctioneer: prefers to sell the good even if at a lower price
• Risk-neutral: neither risk-averse nor prepared to take a risk
Auction Theory
▪ Expected outcome I: English/Dutch/Vickrey/First-price-sealed-bid produce the same
expected revenue to the auctioneer in private value auctions where the values are independently distributed and bidders are risk-neutral
▪ Expected outcome II: among risk-averse bidders, Dutch and first-price-sealed-bid give
higher expected revenue to the auctioneer, because the bidder can insure himself by
bidding more than would be offered by a risk-neutral bidder.
▪ Expected outcome III: Risk-averse auctioneers achieve higher expected revenue via
Vickrey or English than via Dutch or first-price-sealed-bid.
▪ Issues:
• Dishonest auctioneers
• Bidder collusion
• Counterspeculation: getting actual information by talking to people/agents
