Sample Exam Questions

Question 1

answer

Convergence/guaranteed success

executing the mechanism should neccessarily result in its eventual termination, without this property negotions may continue indefinitely.

Maximising social welfare

The mechanism should lead to the best possible total outcome for all parties. (i.e. the sum of utilities of all agents should be maximal)

Pareto efficiency

A mechansim is pareto efficient if it tends to lead to outcomes where no agents benefit at the expense of other agents. An outcome is defined as pareto optimal if all outcomes would lead to a lower utility for any participant.

Individual rationality

A mechanism supports individual rationality, if it is always in the best interests of participants to comply with the protocol, that is a participant is never forced to act in such a way as to ultimatly reduce its own utility. This property should apply to the protocol as a whole, and may not apply in intermediate steps (i.e. an agent may be forced to reduce its utilit

Stability

A mechanism is stable if all participants are compelled (by their expected utility) to behave in a prescribed way, this property allows agents to model the outcomes of protocols in a predictable way. An example of stability is Nash-Equilibrium, whereby one strategy is dominant over others, such that not following that strategy will lead to a reduction in expected utility.

Simplicity

This property may be applied to both the design process of protocols (i.e. designers should choose simpler protocols over more complicated ones with the same behaviour) for obvious reasons. The property may also refer to the computational complexity of decisionmaking witihin the mechanism such that it is tractable for a participant to decide a strategy within the mechanism.

Distribution

Mechanisms should where possible avoid depending on centralised decision making or single points of failure (i.e. a centralised arbitrator), and should take into account the capabilities of and limitations of distributed communication such as bandwidth (i.e. reducing the number of messages exchanged between participants) and communication failures.

Robustness

In the event of a failure of a component (i.e. network failure) , or particpant (i.e. software crash) of the protocol the remaining participants should be able to recover, or resolve the protocol in such a way as to adversely affect the utility of any of the remaining participants.

Question 2

answer

English

• first-price (highest bidder wins, and pays highest price),
• open outcry (participants declare bids to everybody)
• ascending (bid price increases)
• Auction terminates when no bids are received in a given time (i.e. no guarantee of duration or termination.
• Dominant strategy (when agents valuation of goods is certain and other agents valuations are unknown) is to increase price in small increments until agent wins or it reaches their valuation, when the agent withdraws.

Dutch

• first-price,
• open outcry,
• descending (bid price decreases at fixed increments untill lower reserve is met or price reaches zero)
• In some cases bid collisions (where two bids are received simultaneously) leads to a resolution process where price is reset and decreased at smaller intervals with colliding bidders.
• Wihtout collision resolution maximal duration may be decided, with bid resolution duration may not be decidable.
• There is no dominant strategy

First-price sealed bid

• first price
• one shot. (only one round)
• Dominant strategy is to bid less than true valuation.

Vickrey

• second price (Highest bidder wins, but pays the price of the second highest bid)
• one shot. (single round)
• Dominant strategy is to bid true valuation.

Question 3

Question 4

answer

Question 5

answer

decrease uncertainty

because purpose of the institution is to enable a particular kind of interaction, the probability is increased that only agents with co-incident goals will enter the institution

reduce conflict of meaning

the domain of discourse is largely pre-determined by the shared institutional goals, so that alternative meanings are largely precluded.

create expectations of outcome

the purpose of interacting within an institutional framework is because of a desire to achive a certain goal or set of goals, hence objective is shared

simplify the decision process

the possibility space is pruned through the restricted domain and through the shared goal(s), so there are fewer options to consider.

Question 6

answer

ABSTRACT NORMS

vague desires, possibly contradictory, probably unenforceable

CONCRETE NORMS

abstract norms grounded in ontology, open to reasoning

RULES

concrete specifications of (un)acceptable actions, and obligations, declarative style

PROCEDURES

concrete specifications of sequences of actions, options, outcomes

Question 7

answer

1. Although this situation was used as illustration in a lecture, this part of the question is primarily aimed at getting students to apply knowledge in a new (ish) situation.

   Roles: teacher, learner, collaborator

   Scenes: presentation, discussion, question, group-working

   Conversations: a simple protocol situated in one of the above scenes and illustrating a possible interaction

2. abstract: treat others with respect, as you would wish to be treated yourself; learning is useful

   concrete: listen while others are speaking; don't put other people down; engage in the topic being taught; ask relevant questions; rule: if you want to ask a question, raise your hand; if your mobile rings then switch it off;

Question 8

answer

A speech act consists of a performative which indicates the intention of the speech act and a proposition.

kinds are:

representative

inform the recipient

directive

get recipient to do something

commisive

commit speaker to do something

expressive

speaker expresses mental state

declarative

speaker announces something

Question 9

Question 10

answer

Question 11

answer

1. In(x,y) & Grass(x,y) -> Do(cut)
   and
   In(0,0) & Facing(north) & not(Grass(0,0)) -> Do(forward)
   In(0,0) & Facing(south) & not(Grass(0,0)) -> Do(turn)
   In(0,0) & Facing(east) & not(Grass(0,0)) -> Do(forward)
   In(0,0) & Facing(west) & not(Grass(0,0)) -> Do(turn)
   and similarly but differently for other corners
   and
   In(0,x) & Facing(west) & not(Grass(0,x)) -> Do(turn)
   In(0,x) & Facing(d) & not(Grass(0,x)) -> Do(forward)
   and similarly but differently for the other boundaries
   

2. Looking for general evidence of thinking. Hope no one proposes hard-coding the border edges in the same way as the limits of the garden. Simplest solution is probably to arithmetic in the Grass predicate: In(x,y) & Facing(north) & not(Grass(x,y+1)) -> Do(turn) and similarly but differently for facing other directions. Other solutions might involve introducing a new percept earth and perhaps a new predicate Look. Good student might also remark upon the problem of ordering the rules to get the right results and how this gets increasingly difficult as the size of the ruleset increases
3. More evidence of thinking required. Could posit the existence of a radio transmitter in the centre of the garden (doesn't have to be exactly in the centre tho, or really even anywhere near the centre!), then robot can use the gradient effect for navigation (and depositing the grass clippings, so best put the transmitter in the compost heap). The radio-active crumbs should be used now not to reinforce a particular path, but instead to make a robot go in a different direction.

Question 12

answer

Autonomous

This is the key property differentiating agents from say objects, agents should have the capacity to decide for themselves whether or not to take a given action. Agents may be proative (Taking action without explicit external stimulous) and/or reactive (only taking action based on external events) in both cases there is a causal decoupling between elements or events in the environment and the agents actions (i.e. the agent is in some way responsible for its own actions).

Situated in an Environment

Agents are assumed to have some external environment with which they interact. This may be the phisical world, a software simulation or a set of other agents or some other system. The key is that there are things outside the agent which it interacts with that it does not have immediate control over.

Communicative (Also Social Ability)

In the field of software agents a key property is typically the ability of an agent to communicate and exchange instructions and information with other agents.

Mobility

The ability for an agent to move between (sub) environemnts on different machines at different physical localtions

Veracity

It is often common to assume that agents do not give out information which they know to be false

Rationality

Agents decisions may be supported by a sound reasoning

Learning/adaption

Agents may adapt and changee to deal with changes in their environment

Question 13

answer

Algorightmic

• + Simplest (for designer)
• + Easy to understand
• + possible to determine exact behaviour
• - inflexible (hard to deal with interruptions/exceptions/changes)
• - cannot be integrated with learning easily

Declarative

• + individual parts of program are easy to understand
• + Statements may have a higher-level of generality than imperative programs: higher signal/noise ratio
• + Rules may be combined/re-used with little or no modification
• + May be formally grounded
• + New rules may be integrated on the fly ~learning
• - reasoning may be costly/intractable
• - need to manage rules/knowlege to avoid bloat
• - May be hard to understand complete behaviours

Utility-based

• + agent planning simple - just do what least to highest utility out of available actions
• + Allows for flexible behaviours, plans can be immediately abandoned if expected utility changes or high utility action is found
• + Suitable for learning algorithms, use utility as means for guaging/improving performance.
• - Difficult to estimate/model utility in many situations
• - Problems with local minima, may lead thrashing between different activities.

Question 14

answer

• The subsumption architecutre is build using a set of behaviours.
• The behaviours operate in parallel, each takes some sensory and may generate some output (by 'firing') which indicates some action
• The behaviours are composed into layers using an "inhibition relation" which provides a strict total ordering over them, such that a lower-ordered behaviour will override a higher-ordered behaviour.
• Action selection occurs at a given time, by taking all behaviours which have fired, and looking to see if a lower-order behaviour has also fired, thus overriding the output of the orignal behaviour
• The subsumption architecture is representation-free (that is no models of the world are created)
• Action selection in the subsumption architecture has a low complexity (O(N², based on the maximum of the number of percepts or the number of behaviours), so actions can be typically be selected very quickly.
• Despite the simplicity of the components it is possible for complex behaviours to emmerge caused by interactins between layers
• Since no world model is created, agents must have suffient stimulus in order to take actions, it is possible for sensory starvation to cause the agent to stop an agent from doing anything. - The incorporation of internal stimuli (such as timed transitions inside the behaviours) mitigates this to a certain extent.
• Because agents have little or no state, it is difficult to see how agents might take into account non-local stimulus (such as historical events).
• Adapting behaviour and learning is difficult to incorporate
• Complex behaviour is an emmergent property of the interacting individual behaviors, and as such is difficult to engineer
• It is difficult to build agents with many layers, as the interactions between layers become too complex

Question 15

answer

• There are a number of exporer agents and a mother ship
• The task of the explorer agents is to explore a distant planet and to collect samples of a particular type of precious rock.
• No map of the planet is available, but the terrain is known to be such that radio communication between explorers is unlikely to be possible
• The mother ship generates aa radio signal which does not pass any information on to the explorers, but does allow them to locate the mother ship using the gradient of the signal strenght (i.e. the stronger the signal the nearer the mother ship). Agents may then move towards, or away from the mother ship using the signal
• Agents communicate indirectly using radioactive crumbs which may be dropped, picked up and detected by passing robots
• The agent is governed by the following 6 behaviours
  1. if detect obstacle then change direction
  2. if carrying samples and at the mother ship, then drop samples
  3. if carrying samples and not at the base then drop two crumbs and travel up signal gradient (toward ship)
  4. if detect a sample then pick a sample up
  5. if sense crumbs then pick up 1 crumb and travel down gradient (Away from ship)
  6. if true then move randomly
  These are composed as follows (1 being the lowest order (highest priority))
  1 < 2 < 3 < 4 < 5 < 6
• In the absence of any stimulus the agent explores randomly (rule 6), When an agent finds a sample it will pick it up and return to the mother ship and drop them (rules 4,3 & 2). The crumbs serve to reinforce paths to places where samples have been found (rule 5, agents without samples at the mother ship will tend to return to places where samples have beeen found by following the paths of crumbs, however if they find no samples, these paths will tend to deteriorate as the crumbs are picked up but not replaced.
• Benefits of the architecture are: that it is robust (agents are not dependant on each other for action, simple (the rules can be calculated efficiently in real time), and effective (in many cases the architecture leads to near-optimal performance).

Question 16

answer

Tileworld consists of a two dimensional grid, each cell in the grid may contain nothing, a tile, a hole or an obstacle. An agent is placed on an empty cell of the grid, where it may move up, down, left or right. It may not move into cells containing holes or obstacles, agents may move into cells containing tiles, if the cell beyond the block in the direction of movement does not contain an obstacle. If the cell beyond the tile contains a hole then the hole is filled by the tile, and becomes empty. Depending on the paramaters of the experiment, tiles, holes and obstacles may appear with given probabilites at a given time, and my dissapear at a later time. The experiment is run by placing the agent at a point determinied by the experimentor (or at random) and running the envirnment for a given number of steps.

The utility of a an agent's run (i.e. over the duration of the experiment) is defined as a function as follows:

            number of holes filled in r
 u(r) = ----------------------------------
         number of hoes that appeared in r

An optimal agent in tileworld is defined as one which maximises its expected utility over all possible runs. That is in any given environment, the anent always makes decisions which are most likely to lead to the maximum utility. An example might be abandoning the decision to move toward a distant tile, in favour of a nearer one which is less likely to dissapear by the time the agent gets there, or moving to distant regions with more tiles and holes instead of trying to fill local holes will fewer tiles.

Question 17

answer

Agent communication languages are 'outer' languages which are intended to express the general semantics, force and purpose of a mesasge, they typically also indicate the sender and intended receiver (and/or actor to which the message applies), and other properties of the message. Communication languages are typically build based on Searle's Speech-act theory, using a fixed set of Performatives, which characterise a mesage into one of a set of commonly identified interaction types, performatives are common to all agents using a given commnucation language. Additonally mesages contain some content expressed in a Content Language which is given meaning by the enclosing performative. Examples include KQML and the FIPA ACL.

Content languages are used to express properties and queries in a given domain to which the message is relevant. Content languages are typically domain dependant, their structure and semantics are defined by an ontology. Examples of content languages are KIF and FIPA-SL.

Question 18

Question 19

answer

Question 20

answer

Typically planning agents do not build plans from scratch, isntead a plan library is used, consisting of a pre-defined set of plans. Each plan in the library is typically expressed in terms of a set of pre-condidions must be satisfied for the plan to be implemented, a set of actions and a set of post-conditions which will (probably) be satisfied when the actions are executed.

Plan selection within an agent can be done by running though the plans and find those who's post-conditions unify with one or more of the agents intentions, and whos pre-conditions unify with the agent's current beliefs.

Question 21

Question 22

Question 23

Question 24

Question 25

Question 26

Question 27

Question 28

Question 29

Question 30

Question 31

Question 32

Question 33

Question 34