2019 Flashcards
four properties that you consider more relevant for an agent.
Reactivity
Reasoning
Learning
Autonomy
main properties that an interface agent should have.
Autonomy
Learning
Proactiveness
Explain how the Contract-Net protocol works.
The contract NET protocol is a task sharing protocol in MAS.
- Recognition: agent recognizes it has a problem and needs help to reach the goal.
- Announcement: agent sends an announcement with the specifications of the task
- Bidding: agents that receive the announcement decide if they want to bid. If they do, they submit a tender (conditions for executing the task)
- Awarding: the agent that announced the task decides who to award the contract to and the other bidders are informed.
- Expediting: the successful contractor expedites the task.
three basic relationships between tasks considered in the Generalised Partial Global Planning method.
ENABLES
A enables B: A must be executed before B
FACILITATES
A facilitates B: executing A makes possible to solve task B more quickly and with more quality.
HINDERS
A hinders B: executing A implies that solving B will take more time and the solution will have less quality.
Describe a voting method explained during the course that does not have the property of unanimity.
The property of unanimity (pareto efficiency) states to not misorder the options if all agents agree. For example, if everybody thinks that A is better than B, A should be preferred to B in the aggregated order.
In binary voting all options are ordered and then evaluated in pairs. The option that wins the last evaluation is the overall winner like
win(o5,win(o4,win(o3,win(o2,o1))))
Because the order of the pairings affects the outcome, the last options have higher chances of winning. It is possible that an alternative wins that wasn’t the first choice for anyone. This violates the unanimity property.
Explain the similarities and differences between First Price Sealed Bid and Vickrey auctions.
In FPSB auctions each bidder submits its own sealed bid without knowledge of the bids of others (bidding phase). Then the bids are opened and the highest bidder wins (resolution phase). The winner pays the amount of its bid.
Vickrey auctions are similar as each bidder also submits its own sealed bid without knowledge of the other bids. The bids are opened and the highest bidder wins like in FPSB, but with the main difference that the winner pays the amount of the second highest bid.
The best strategy in FPSB would be to not bid the true valuation but a small amount below it, while in Vickrey auctions the best strategy is to bid the true amount. Although it seems that the auctioneer would make more money out of a FPSB auction, this is not the case as bidders adjust their bid upwards in Vickrey auctions because they not not have to fear that they will pay too much.
Which is the difference between external and internal coalition formation algorithms?
External coalition formation is performed by imposition by an external entity, while internal coalitions are established by self-organization through group interactions of agents.
If a coalition formation is done externally, agents advertise skills and prices to an external entity, the entity computes optimal coalitions and forms a coalition.
On the other hand, within internal coalition formation, agents communicate with each other, negotiate tasks and form self-organized coalitions.
- Explain briefly how an electronic institution is used to model the behaviour of the agents of a multi-agent system.
An e-Institution is the computational model of an institution through
- The specification of the institution’s norms in some suitable formalism
- The formal specification of the institution’s admissible procedures and protocols, which follow the established conventions
In the context of MAS, e-institutions:
- reduce uncertainty about other agents’ behaviour
- allow agents to foresee the outcome of an interaction
- simplify the decision making process (by reducing the possible future actions)
The behavior of the agents is regulated by Norms
Comment briefly the main characteristics of the kinds of problems that can be solved using multi-agent systems.
1 Distributed and decentralized scenarios
- where knowledge and control are distributed geographically.
- where restrictions on information sharing apply
- where competition between different actors is given (e.g. e-commerce)
- where a time-critical response and high robustness are needed (e.g. manufacturing)
2 Simulation and modeling problems like traffic flow
3 Open and dynamic systems
4 Autonomous systems where the user delegates the decision making authority to the system
5 Complex systems: where the decision making process implies the decomposition of problems, internal reasoning of the agents and the use of cooperative problem solving techniques
main differences between deliberative and reactive agents
Reactive agents are focused on fast reactions to changes in the environment, while
Deliberative agents are focused on long term planning of actions, centered on a set of basic goals.
Reactive agents rely on a behavior-based paradigm. Each behavior continually maps perceptual input to perceptual output. Deliberative agents have a sense-plan-act problem solving paradigm.
In reactive architectures there is at most a very simple internal representation of the world. In deliberative architectures, there is an explicit symbolic model of the world
Basis steps in distributed problem solving
1 TASK DECOMPOSITION
Divide a complex problem into a set of tasks. Decompose large tasks into subtasks that can be tackled by different agents
2 TASK ALLOCATION
Assign the subproblems to different agents
3 TASK ACCOMPLISHMENT
Each agent solves its assigned subproblems.
(+ conflict management if there are dependencies between tasks)
4 RESULT SYNTHESIS
Put together the results of all agents to find the complete solution
Advantages and shortcomings of blackboard communication
- Detect conflicts
Different agents that want to perform the same task - Notice incompatible solutions
Solutions using a shared resource at the same time - Share results
Agents can use partial/complete results obtained by other agents - Share tasks
Agents can request help in solving sub-tasks
+ Flexible mechanism that allows communication/cooperation
+ Independent of cooperation strategy
+ It does not place any restriction on the agents’ internal architecture
- Centralised structure
- System bottleneck
- Everyone has to write info on the blackboard
- Everyone has to read from the blackboard
- Single point of failure
What is a coalition? Which is the purpose of a coalition formation algorithm?
Coalitions are (temporary) collections of individuals working together for the purpose of achieving a task. Coalition formation is the process where by an agent decides to cooperate with other agents, because
- the task cannot be performed by a single agent
- the task can be performed more efficiently by several agents working together
Coalition VALUE CALCULATION
Calculate the benefit of each coalition for each task
Coalition STRUCTURE GENERATION
Decide the coalitions to form, maximizing thecoalition value
PAYOFF DISTRIBUTION
Deciding howto distribute the payoff betweencoalition members (equally, outputs, role)
