Institutional Robotics and Norms in Multi-agent Systems

The field of Affective Computing has achieved great advances in Artificial Emotional Intelligence, the artificial counterpart of Emotional Intelligence [1]. Reacting emotionally according to the human emotions perceived through observation and dialog has been achieved. However, there are two key points that, to the best of my knowledge, these proposals are ignoring:

1. Multi-Human Multi-Computer Interaction: Sometimes it is required interactions among more than one computer or one human. For instance, in the field of Ambient Intelligence, there may be situations that whatever the system performs upsets one user or another, e.g. activate lights on door crossing while another user is sleeping. The current approach would be manually create rules avoiding this behaviour. However, the system might learn this rules according the emotional reaction of the users in front of these situations. Cases of multi-computer multi-human interaction occur frequently in offices where computers might detect decreases in motivation of employees and react accordingly.
2. Proactive Affective Behaviour: Similarly, there are cases when reactive emotional behaviour is not enough. In the example of Ambient Intelligence, the system might propose pro-actively to show certain films according the current emotional state of the user(s) (e.g. stressed) to achieve an emotional goal (e.g. relaxed users). In the case of offices presented, the computers might cooperatively propose short breaks to the most stressed employees (e.g. visiting the coffee machine where the latter can meet and have a relaxed short talk).

Implementing the last one would have many applications for example in:

• Entertaintment: to endow agents the capability  to search certain appraisals from other agents and users (e.g. funny) but also certain emotional responses (e.g. or even caress with the appropriate sensors)
• Negotiation: to create agents capable of trying to convince (or persuade) other agents or humans using its Artificial Emotional Intelligence to take advantage of the emotions perceived on others.

However, “great power brings great responsibility” and we  cannot expect agents to blindly serve its user and always act  responsibly at the same time. This is when meta-norms come handy too.

In my opinion, as emotions partially regulate our perception and behaviour, norms about them acquire the status of meta-norms.

Examples of meta-norm referring to emotions might be:

Forbidden to yell at other agent i if agent i’s emotional state is mainly sad especially if crying.

These meta-norms might be further refined with ontological rules defining specific topics that are desirable to be regulated in certain conditions:

Agent j is forbidden to yell y at other agent i if agent j’s emotional state is mainly angry, y is a type of name-calling and agent i’s emotional state is mainly sad.


References

[1]	Daniel Goleman. Working with emotional intelligence. Bantam, Toronto, 1998.

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

Coordination under the assumption of sharing information about Trust and Reputation might be formalised as a Interactive Partial Observable Markov Decision Process (I-POMDP).

“I-POMDPs generalize POMDPs to handle the presence of, and interaction with, other agents. This is done by including the types of the other agents into the state space and then expressing a belief about the other agents’ types.” [1,page 21]

“[…] Thus, (I-POMDP) is closely related to partially observable stochastic games (POSGs). In contrast to classical game theory, however, this approach does not search for equilibria or other stability criteria. Instead, it focuses on finding the best response action for a single agent with respect to its belief about the other agents, thereby avoiding the problems of equilibria-based approaches, namely the existence of multiple equilibria.” [1,page 20]

However, to solve these problems seems at least as hard as solving Dec-POMDPs and therefore intractable with no further assumptions:

“Even with both approximations (i.e. finite nesting and a bounded number of models), I-POMDPs seem to have a double-exponential worst-case time complexity, and are thus likely to be at least as hard to solve as DEC-POMDPs”. [1, page 25]

Here models refers to agent models and not to trust models:

“Definition 23 (Models of an agent): The set of possible models of agent j , Mj , consists of the subintentional models, SMj , and the intentional models IMj . Thus, Mj = SMj ∪ IMj . Each model, mj ∈ Mj corresponds to a possible belief about the agent, i.e. how agent j maps possible histories of observations to distributions of actions.

• Subintentional models SM j are relatively simple as they do not imply any assumptions about the agent’s beliefs. Common examples are no-information models and fictitious play models, both of which are history independent. A more powerful example of a subintentional model is a finite state controller.
• Intentional models IM j are more advanced, because they take into account the agent’s beliefs, preferences and rationality in action selection. Intentional models are equivalent to types.” [1, page 21]

Previous work not mentioned in the quoted article reports that exact results are obtained solving I-POMDPs using behavioral equivalence with a complexity similar to solve POMDPs [2].

Im my humble opinion, with further assumptions, as full observability of states and actions  by a centralised middleware and non-nesting beliefs about others represented in states, the problem may be reduced to n MDPs which have polynomial time complexity. However, this reduction may not always be desirable as it requires an appropriate infrastructure.

Opinion Edit:
I believe that the omission of the latter paper in the former journal article is due to the long review processes that journal articles have to overcome and not due to an error of the authors.

References

[1]	Sven Seuken and Shlomo Zilberstein. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 17(2):190-250, 2008.

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

Decentralised coordination under partial observability (formalised as Decentralised Partial Observable Markov Decision Process (Dec-POMDP)) is proven to be computationally intractable [1].
Although increasing the number of assumptions such problems may be solved even in polynomial time [1], norms may reduce both the (valid) action and (valid) state space thus reducing convergence time of such algorithms.

Thus, not to follow a norm might imply never reaching to coordinate with the rest of agents and/or to be punished with a sanction. Then, to preserve the interests of the group trying to coordinate in the former cases, the group may decide to expel the agent from the group as proposed in [2].

However, instead of applying ostracism by group decision each time this occurs (another Dec-POMDP), a meta-norm enforcing ostracism may be deployed in a distributed manner and if it is enforced locally to the agent, the chances of coordination of the group are preserved:

If an agent A violates N times norm I, then A is expelled from group G working on activity X.

References

[1]	Sven Seuken and Shlomo Zilberstein. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 17(2):190-250, 2008.

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

Institutional Robotics is a new view of an old topic. The idea that robots may be regulated by laws (or norms) was extended by Isaac Asimov’ sci-fi books in the mid of 20th century.

In the 90s, Philosophy Professor John Searle contributed with the idea of Social Reality, i.e. there exist brute facts, as the height of a mountain, and institutional facts, as the score of a football game. Furthermore, he stated that institutional facts are constructed with logical rules of the form “X counts as Y in C”.

With these two notions, we defined brute and institutional events. Whereas brute events are unavoidable and performed by agents, institutional events are the subset of brute events that is considered valid in a given context, namely the institution.

For instance, waiving a hand counts as a greeting in most situations but it may count as a bid in the context of an English Auction.

With these notions, we are able to enforce norms as translations of brute events to institutional ones that cause changes in the context (or institution) where the event was generated.

Then, I propose Institutional Robotics as the enforcement of norms in possibly adversarial teams of robots using the concept of institution in Searle’s sense. To read about a proposal that completely ignores all previous and seminal work in Electronic Institutions, Virtual Organisations, and norms in Multi-agent systems, even when the former is partially published in an agent conference, check here.

In order to explain Institutional Robotics in plain English, I will use the movie “The Matrix”.Institutional Robotics is to force robots to be in a Matrix controlled by humans and enforced by agents. However, our Matrix will be more human, as they will have a partial view and partial freedom to act (controlled by us) in the real world.

Then, I propose that robots must interact in Controlled Reality, the mix of Augmented Reality and Parental Controls.

(I only hope that a robot like Neo will never exist! )

I’ve designed a robot architecture for Institutional Robotics based on a new type of Electronic Institution that I call Cooperative Electronic Institutions. I’ll explain more on this, if the paper describing this gets published.

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

Recently, I read about the PEIS project. They provide a hardware abstraction middle-ware in order to program devices in applications of Ambient Intelligence. They provide the code and tutorials on how to create your own controllers.Now suppose you installed this awesome intelligent and cooperative system at home and a pranking friend gives you a new intelligent toaster that perfectly integrates with the PEIS system that you just installed.

Comic strip extracted from PEIS Tutorial
Your so-called friend might have modified the toaster controller to function almost correctly but in random situations it would interfere with the system in order to play pranks on you.This friendly example is one of many showing the importance of applying Institutional Robotics in our robot research.Cheers!

Edit: I admit that the current approach of digitally signing the code may avoid some attacks. However, if we develop intelligent devices taking spoken orders from their owner, we will not be protected from pre-trained toasters sent by pranking friends (unless we agree on the importance of applying Institutional Robotics on them)

Edit 2: If we would follow Conspiracy theory and do not solve this, in a not so distant future we should not bring home any gift (including cash) from banks, governments, etc. (the so-called friends) even if they gave them to us because we are a very “special” client or citizen. Their real goal might be using them to extend the scope of their spying and controlling technologies.

Edit 3: I may say that including RFID into cash might end some frauds to the Treasury and robberies. However, thieves with the proper technology might also be capable to easily select a victim.

Conclusion: any technology capable of spying and controlling should be regulated by a neutral and trustworthy party in order to give only legitimate access to these capabilities.

Edit 4: In my humble opinion, access control should not only be based in who access the capabilities but also what for and in what context. For instance, you might allow your personal robot to wave a hand at your pranking friend’s command to greet another friend. But you hardly would allow this in auctions selling items you do not want to buy.

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

In order to explain Institutional Robotics in plain English, I will use the movie “The Matrix”.

Institutional Robotics is to force robots to be in a Matrix controlled by humans and enforced by agents. However, our Matrix will be more human, as they will have a partial view and partial freedom to act (controlled by us) in the real world.

Furthermore, in the movie, humans are connected to a centralised Matrix and therefore they can disconnect. I propose Institutional Robotics to be a peer-to-peer Matrix embedded in robots during their construction so robots and the norm enforcement mechanism cannot be separated.

Then, I propose that robots must interact in Controlled Reality, the mix of Augmented Reality and Parental Controls.

We cannot prevent neither military nor terrorist (nor pranking) use of robots. However, its use might be regulated by neutral and trustworthy organisations as the ONU and enforced through Institutional Robotics. For instance, robots are forbidden to kill civilians. More applications here.

I only hope that robots like Neo will never exist! :S

More in Institutional Robotics here.

Hope this post helps to clarify this notion,

Cheers!

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

Taking science-fiction movies and literature as source for unreal and unspecified related work, we have to mention Asimov’ Laws of Robotics.

The four laws stated:

• 0 - “A robot may not harm humanity, or, by inaction, allow humanity to come to harm.”
• 1 - “A robot may not injure a human being or, through inaction, allow a  human being to come to harm, except where such orders would conflict with the Zeroth Law.”
• 2 - “A robot must obey any orders given to it by human beings, except where such orders would conflict with the Zeroth or First Law.”
• 3 - “A robot must protect its own existence as long as such protection does not conflict with the Zeroth, First or Second Law.”

In my humble opinion, Asimov’ Laws have an open interpretation, are not politically correct and require a more specific update.
For instance, how many human beings are allowed by the First Law to be killed by robots to save humanity from pollution without “harming humanity”?
Are cars and gas trucks allowed to be destroyed by robots to save humanity from pollution?
Are gas stations allowed to be controlled by robots in order to prevent us from using them?.

Then, norms also tend to get obsolete so we need a regulated mechanism to create and modify norms. This is were meta-norms are useful.

Meta-norms are norms referring to other norms. For instance, Robert Axelrod [1] provided the example of having willingness to punish someone who did not enforce a norm. Thus, we will use meta-norms to regulate how to regulate robots.

More about the application of meta-norms in Institutional Robotics will be presented in my next paper so please be tuned.

References

[1]	Robert Axelrod. An evolutionary approach to norms. The American Political Science Review, 80(4):1095-1111, 1986.

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

Recently, a lot of effort is being made to research “agreement technologies”. As (almost) everything may be represented and implemented by semantic rules, one may call them “semantic technologies”. However, it is not very specific as we cannot give meaning to everything in short term. Then, accepting the specific name, we accept the research is about agreements.

In my opinion, agreements are just norms resulting from negotiation (then agreed) and different from laws (imposed norms).

By norms, I mean rules describing how to behave and how to be. There are a lot of works studying how the first ones emerge and implementing them in multi-agent systems. The last ones are ontological rules specifying how something has to be in order to be related to others. For instance, to be considered a female mammal (and be related to other mammals), an animal has to possess mammary glands among other conditions. A social example would be, to join certain high society club, you must be either rich or famous (the latter notions also need to be specified with semantic rules).

Then, agreements and semantic alignment can also be seen as the negotiated creation and modification of ontological and behavioral rules. As Virtual organisations (and Electronic Institutions) may be seen as the enforcement of such rules, these “agreement technologies” can be reduced to negotiation that changes norm representation and enforcement. However, we expect negotiation (even including argumentation) to be regulated by some ontological and behavioral rules.

Thus, in my opinion, all these topics may also be achieved with (meta-)norms on how to change norms. Then, another possible name for that research effort may be “meta-norm technologies”.

I will reveal more on “meta-norm technologies” in my next paper, so please stay tuned.

Cheers!

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

The goal of this post is to find better applications for Institutional Robotics. I present some of them and I will be updating the list. Please feel free to comment and increase this list. All your contributions will be credited.

• Defense Regulation: we cannot prevent military use of robots. However, its use might be regulated by neutral and trustworthy organisations as the ONU. For instance, robots are forbidden to kill civilians.
• Civil Regulation: in case robots were used by civilians in common-life tasks, they might be also regulated by each country in order to prevent misuses. For instance, prevent robots to steal, harm, kill, etc. following the orders of its owner.
• Self-Refereeing in RoboCup: adversarial teams of robots are currently being developed to play soccer, but the referees are still humans controlling robots remotely. A global view of the match, namely all sensor data from all robots, might be used to enforce the rules of the game transparently to robot reasoners [1, Future Work, New applications of norms].
  
  
  Aibo robots playing soccer
  An extract of my thesis, section New applications of norms:
  […]In this thesis, following the Electronic Institutions tradition we applied in our examples the regulation of Multi-agent systems (MAS) to e-commerce, mainly to auctions. However, we want to find and exploit new interesting applications of norms in MAS that may lead to enrich the current model. We envisage its application in robot soccer and autonomic networking.
  A question in the field of robot soccer that we find interesting is: how robots could autonomously play soccer without a referee? To solve this we envisage a software layer common to robots of any team. This layer would act as a middleware between the hardware layer, that deals with motors, rotors, sensors, etc., and the reasoning layer, that according with the information of the hardware layer generate an individual or team plan that is transformed in commands to the hardware layer in order to play. This middleware would follow the metaphor of institution but distributed in all robots to enforce some global rules. As a literary example, the reader may think of the hard-coding of Asimov’ three laws of robotics in the “brain” of every robot. However, the programming of the reasoning layer would be available of end-users, as human coaches in the case of robot soccer. This topic requires further exploration as, for instance, norms could vary in time possibly as result of the execution of protocols. For instance, soccer rules may change from season to season due to some recurrent unwanted behavior of players.[…]

Institutional Robotics and Norms in Multi-agent systems by Andrés García-Camino is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Spain License.
Based on a work at blog.garcia-camino.es.

The idea of this blog is to share thoughts and advances in Norms in MAS and Institutional Robotics. Please feel free to share yours.

Happy New Year!