Law-governed interactionBackgroundIntroductionCoordination with lawsPrinciple 1: EnforcementPrinciple 2: DecentralizationPrinciple 3: Separation of policy from mechanismPrinciple 4: Incremental deploymentDiscussionFormalismDetailsEEL 5708Law-governed interactionLotzi BölöniEEL 5708Background•Based on the work of Naftaly Minsky and Victoria Ungureanu at Rutgers University–The Moses toolkit•I find it interesting because it makes us look in a different way to the world of agents•You may find “laws” in other agent frameworks, simulation frameworks and games as well.EEL 5708Introduction•Societies of agents need to be coordinated “the managing of dependencies between agents in order to foster harmonious interaction between them” (Malone and Crowston 1994)•“a flock of birds must coordinate its flight in order to stay in formation”•Example of coordination policy: Budgeted Consumption–A client X can present a query to the database only if it has a positive budget bx, available to it, and bx is reduced by one for each such query. –Budgets can be provided to individual clients by a designated regulator, and a client with a positive budget can give part of it to any of his peers.EEL 5708Coordination with laws•The authors propose several principles regarding the implementation of multi-agent coordination. •The enforcement needs to be decentralized•Coordination policies need to be formulated explicitly (rather then implicitly in the code of the agents)•It should be possible to deploy and enforce a policy incrementally, without exacting any cost from agents and activities not subject to it.EEL 5708Principle 1: Enforcement•“A coordination policy for an open group need to be enforced”•Security issues•Disparate members of an open group which might have been built independently might have little reason to trust each other.EEL 5708Principle 2: Decentralization•The enforcement mechanism should not require central control. •Easiest, with a centralized coordinator. –Not scalable, the coordinator is the bottleneck–Single point of failure.•Many laws are local in nature (for instance the one about budgeted consumption)EEL 5708Principle 3: Separation of policy from mechanismCoordination mechanisms should be made explicit, and be enforced by the means of a single mechanism that can implement a wide range of policies in a uniform manner. •Large, conglomerate systems are likely to employ many different coordination policies. •A single agent might need to operate in multiple groups, not foreseen during its designEEL 5708Principle 4: Incremental deploymentOne should be able to deploy and enforce a policy incrementally, without exacting any cost from agents and activities not subject to it. •In a large system, if deployment cannot be done incrementally, without making any requirements of the rest of the system, it probably cannot be done at all.EEL 5708Discussion•Are the principles reasonable?•Do they match what happens:–On the internet?–In the human society?–Animal world?EEL 5708Formalism•Law Governed Interaction (LGI) is a mode of interaction that allows a heterogeneous group of agents to interact with each other with confidence that an explicitly specified set L of rules of engagement – called the law of the group – is complied with. •“L-group” G <L,A,CS,M>–L law – an explicit and enforced set of rules of engagement–A a set of agents members of the group–CS a set of control states, one per member of the group–M a set of messages that can be exchanged, under law L between the members (L-messages)EEL 5708Details•The law of a given group G is global with respect to G, but it is defined locally at each member of it. •The law is defined over certain types of events at the agents, mandating the effect that any such event should have. Events include sending and receiving messages.•The ruling of a law for an event e depends only on the event e and the control state CS of the agent.•The ruling of the law at a