Multi-agent Systems: Agent versus Terrain modeling

Multi-agent Systems - I

Recall that the objective of designing multi-agent systems (MAS) may be summarized as: engineering emergence. A multi-agent system comprises of several agents acting autonomously seeking to maximize their self-interest functions. The behaviour of agents interfere with one another and it is this interference -- or emergent characteristics -- that is molded by the system designer to achieve desired system-wide objectives.

Any multi-agent design problem can be viewed from two extremes. I'm calling these extremes as: the agent-design perspective and the terrain-design perspective.

In a MAS problem that is of the former kind, the designer has complete control in designing the agents and their rational strategies. The designer would have negligible or no control over the environment in which the agents perform -- the logical or physical space that determines how agents interfere with one another.

An example is the design of a swarm of robots that are deployed in disaster recovery efforts. The designer has full control on how to design the robots so that they can behave autonomously and compete/collaborate with one another to achieve a given objective. However, the designer has no control on how the terrain is likely to be. Each disaster zone is unique, and poses its own challenges. The design challenge here is in ensuring autonomous behaviour such that the robots can achieve their objective regardless of what kind of situation they are in.

The second extreme perspective for MAS design problems is the terrain modeling problem. Here, the designer has little or no control on the behaviour of agents themselves. However, the autonomous agents act within the boundaries of a (logical or physical) "terrain" over which the designer has complete control.

Consider that you are building an online marketplace involving a service like travel coupled with social networking facilities. (An example site that comes close is TripIt.com) Here, agents are real people pursuing their own self interest objectives on the site (business travel, vacation, etc.) There could be different agents (business people, vacationers, travel agents, etc.) each having their own distinct objectives.

The objective of the designer in this case, is to maximize the number of agents who are happy (and/or maximize the objectives that bring in the most revenue). At the same time, the designer has to minimize or prevent undesirable interferences among agents.

Instances of the latter kind of problem can be seen in several environments involving multiple people interacting -- be they multi-user operating systems or design of brick-and-mortar public places like railway stations.

Agent modeling can be thought of as being rooted in areas like game theory, negotiation theory, auction theory, etc. On the other hand, terrain modeling has its roots in mechanism design, design of normative regulatory or governance frameworks and even in physical modeling of spaces.

Most MAS design problems have elements of both agent and terrain modeling problems. There is perhaps a lot of designer instinct that needs to be developed in order to determine where exactly to draw the line between terrain and agent modeling.

For instance, consider that agents in our problem are human beings and the MAS problem is to regulate traffic flow on the roads of a city. This is a problem that is predominantly of the terrain-modeling kind. The designer has no control over the minds of the people -- what are they thinking and what are they seeking when they are driving on the roads.

The terrain modeling hence takes two forms: a "physical" form, which is the design of the road network itself and a "normative" form which are the traffic rules, one-way streets, turn-restrictions, etc. However, this problem also has an element of agent modeling -- in the form of the requirement for a driving licence. Agents in this case are "modeled" (trained) so that they obtain proper reflexes and learn good driving, before they can use the system.

But for several sub-problems of the traffic design problem -- like driving etiquette, for example -- it is quite a challenge to get the right balance between agent modeling (creating awareness) versus terrain modeling (creating and enforcing rules for driving etiquette).

Multi-agent Systems: Machines versus Societies

Jut thought I'd start a blog-post series on multi-agent approaches to designing systems. We discuss several ideas in the class on multi-agent systems, most of which are forgotten because they are not documented. This series is aimed to fill that gap and document some of the ideas that have floated around in class.

Machines versus Societies

Even a cursory look into machines built by nature (living beings) is sufficient for us to realize that engineering principles used by nature are fundamentally different from the engineering principles we use.

For instance, the wheel is considered to be one of human-kind's most basic invention. Yet, nature does not have wheels. Not just wheels, it is rare to see rotary motion in nature as well. There are no natural occurring motors, turbines, pistons, etc.

Similarly, birds don't have engines. They don't need runways to take off and land. Animals don't need roads and highways to move.

Naturally occurring machines are made to adapt to their surroundings, in contrast to artificially built machines, for which the surroundings are adapted for their use.

Nature seems to favour adaptability and resiliency more than sheer mechanical power, computational speed or efficiency.

In fact, nature is far ahead in building highly resilient machines, than the best of our engineering practices. My favourite example is of the human heart. The human heart beats at the rate of 70 beats to a minute. It is a mechanical device, performing physical actions. Like all mechanical devices, the heart is also prone to wear and tear. Yet, our heart beats continuously at this rate for our entire lifetime -- without stopping for sleep or hibernation and without the need for maintenance and servicing every six months.

The common engineering principle that brings about these traits in natural machines is that these machines are built in the form of societies of autonomous agents -- rather than a mechanical contraption serving a particular purpose.

Our bodies are built by fundamental elements of life called cells. Cells are the smallest "living" element in our bodies -- just like the entire animal, cells are autonomous creatures that strive to enhance their own survival. Cells compete with one another for resources, and also form strategic collaborations with one another when this aids their own survival.

Cells forming the human heart for example, participate in making the heart beat -- not because they were designed to do so, but because participating in this activity is the best choice each cell can make to increase its own survivability. Every cell that makes up the heart has to contract and expand in a synchronized fashion, in order to make the heart beat. This synchrony by each cell is not "pre-programmed" into the cell, but is decided by "autonomous choice" (the so-called illusion of free will). The evidence to the fact that this choice is autonomous, is a condition called ventricular fibrillations. This is a condition where cells in the heart are beating, but this isn't helping the heart pump blood. Fibrillations are usually alternate stable states for the cells' actions -- except that these states do not pump blood, and the organism can experience sudden death.

Designing large systems as societies of autonomous agents, has several benefits. Such systems can display complex properties like self-healing, complex control and adaptability, learning, self-reconfiguration, etc. For instance, a dent on our car doors would require major tinkering work for its repair. However, a "dent" on our skin (a cut), would result in a number of autonomous actions by cells affected by the dent. If the dent were bleeding, blood cells that are exposed would clot, the skin cells that were lost would be replaced by cell reproduction from neighbouring cells; and the "dent" would be gone by itself in some days.

Societies of autonomous agents also display emergent characteristics -- characteristics of the system that cannot be attributed to any of the constitutient agents. For instance, our thoughts, cogitations, dreams, etc. are emergent properties of the functioning of our brains. They are there because of the dynamics of the neural interactions in our brains, rather than a property of any individual neuron.

The multi-agent design problem can hence be formulated as: engineering emergence. As engineers, we build systems with an end goal in mind. Our systems should display certain characteristics and comply with design specifications. However, a multi-agent system should achieve this by each individual agent working autonomously -- in its own self interest -- for itself.

Characterizing emergent behaviour is hard -- typically intractable by conventional computing because of non-linear interdependencies between the dynamics of the agents. But several naturally occurring chaotic (non-linear) systems (like the weather, for example) have shown that they can function within stable regions of their state spaces, even though their exact trajectory within this space would be practically impossible to characterize.

Engineers of multi-agent systems should also expect somewhat similar characteristics from multi-agent systems. It may be possible to build multi-agent systems that are guaranteed to work within bounded (stable) regions of their state spaces. But the exact behaviour within this region may be impossible to characterize.

The end of the desktop and browser?

Imagine this scenario: You open your laptop and boot up the operating system and login. Once you login though, you don't see the familiar desktop with the Start button. Instead you see your virtual "living room."

The "living room" has a sofa set, a television that runs YouTube, and at the other end of your living room is your office desk. On the office "desktop" is a cabinet containing "My Documents." You then open the cabinet and choose the file you had to review.

But of course, the sight of your office desktop makes your brain go numb. So instead of sitting there and reading the paper, you decide to go up the stairs onto the terrace. On the way to the terrace are other rooms of your "house" where you have some apps and documents lying around. The walls adorn pictures of your family and from your last vacation.

The terrace looks out into the neighbourhood. Your "house" is in a very scenic location that you always wanted. There are mountains in the background, there is a river running across, birds flying and the sun is shining bright. Your neighbourhood is your subnet and each house has its number (IP address) on its main door. The neighbourhood offers several services at its community center like DHCP, which you can avail of by just flying over to the community center. Often machines in your house will do the job for you so you don't have to worry about it; but once in a while, you may have to visit the community center yourself. The community center is also networked with other community centers and has a nice supermarket, usually having a wide array of freeware goodies that you can choose from. If you don't find what you want, don't fret. The community center network is equipped with state of the art searching tools like distributed hash tables, fuzzy search systems, de-duping systems, etc. You can search very easily across all the centers in the network and request at your local center.

Coming back to your terrace, there is also a small basketball court where you could shoot a few baskets. But you have work to do and you sit down on the couch and open the document to review.

After finishing the work, you walk across to the parapet wall and notice your friend on his terrace playing with his basketball too. Two more of your neighbourhood folks are walking to the river for a boat ride. A couple of them are playing badminton at the playground.

You decide to say hello to your friend, so you fly over to his terrace (of course). You can land on your friend's terrace, and also enter his house a little bit; but of course only to those areas that he has explicitly made accessible.

You notice that your friend is not alone and there are a few more people in the house. They all share the same house because they just login using dumb terminals and xdm onto the same system.

Your friend has two tickets to the sitar recital happening at the city auditorium. The sitar recital is really happening -- in the real world and it is going to begin at 6:00pm. In your world though, it is being beamed at the virtual auditorium. You can of course fly to the auditorium, but even that is too tedious. The ticket contains a teleport service and clicking on it instantly transports you to the auditorium.

The concert is yet to begin, but you see other music lovers already milling around. You spot your colleague there who in his real life is presently out of the country on a project. But being the avid music lover that he is, he attends many of the concerts back home virtually.

You chat for a while with your friend and go into the auditorium and take your seats. The lights are dimmed and the main screen comes into focus. A flash video stream of the actual sitar recital then starts.

The virtual auditorium is quite big -- it can accommodate about 200 people. And this is decided based on the bandwidth of the auditorium server of course! :-) It can also be rented out for conferences and workshops and other events. The main screen supports a number of different services -- it can display powerpoint slides, flash animations, videos and can even be used as a whiteboard.

=================

None of the above are futuristic ideas. Several people lead such lives at SecondLife, There and several other virtual worlds already. Except that in the future, it is going to get more integrated into your machines, desktops, LANs and so on.

Bandwidth, you ask? 3D acceleration, you ask? Well the answer to the first is vector graphics and/or compression techniques. And VirtualGL is a possible answer to the second. We're already taking baby steps in that direction. 3DNA is one example for Windows desktops.

Real men and hardcore programmers don't use virtual worlds you say? No problem, you guys said the same thing about GUIs and graphical desktops as well. No one takes you seriously, anyway. :-)

And why are 3D environments important? Because as human beings it is the most natural space for us. Showing a flat vertical screen and calling it your "Desktop" is anyday less desirable than actually showing a desktop.

Co-occurrence and Correlation

In one of our projects, we encountered this dilemma where we had to nitpick on (the probability of) co-occurrence of a pair of events and correlation between the pair of events.

Here is my attempt at disambiguating between the two. Looking forward to any pokes at loopholes in my argument.

Consider two events e1 and e2 that have a temporal signature. For instance, they could be login events of two users on a computer system across time. Let us also assume that time is organized as discrete units of constant duration each (say one hour).

We want to now compare the login behaviour of e1 and e2 over time. We need to find out whether e1 and e2 are taking place independently or are they correlated. Do they tend to occur together (i.e. co-occur) or do they take place independent of one another?

This is where terminologies are freely used and things start getting a bit confusing. So to clear the confusion, we need to define our terms more precisely.

Co-occurrence is simply the probability that the events e1 and e2 occur together. In other words, this is the joint probability of e1 and e2. Let's represent this as p(e1,e2). The joint probability of a pair of random processes A and B is defined as:

When we are talking about temporally distributed processes like e1 and e2, the intersection is simply the number of times e1 and e2 have occurred in the same time bucket and the union is the total number of times e1 or e2 have occurred (counting the co-occurrences only once).

Another form of measuring relatedness between the events e1 and e2 is to compute their correlation coefficient. Correlation measures the linear relationship between pairs of random variables.

Intuitively, suppose our time units were divided into discrete buckets t1 .. tn. In each time bucket, we have counted the number of times e1 and e2 have occurred. We now take a 2-dimensional plot and for each time bucket, we place a point on the plot, whose x and y values are the number of times e1 and e2 have occurred respectively.

(Here there is an implicit assumption that the resolution of our measurement is the width of the time bucket. That is, if the time bucket is 1 hour, it does not matter when exactly an event occurred in that hour.)

Given this scatter plot, if we can now draw a line passing through all the points such that the error between the points and the line is minimal, we say that the events are (linearly) correlated. A popular way of computing this line is to use the Pearson coefficient.

The correlation coefficient takes into consideration similarity in occurrences across each bucket. The scatter plot can also reveal specific patterns of correlations that cannot be discerned by the probability of co-occurrence. For instance, suppose that if the events e1 and e2, co-occur, they co-occur not more than 5 times within a time bucket or not co-occur at all. This peculiarity is lost in the co-occurrence computation.

On the other hand, the co-occurrence probability gives an easy way of summarizing pairwise relationships in a large set of events. It is also easier to build generative models and synthetic data sets that reflect co-occurrence probabilities than those that reflect co-occurrences (I think).

There are many other ways to compute relatedness. One other metric worth mentioning here is the mutual information metric between pairs of events. This is a small but significant addition over computing the joint probability. Intuitively, the mutual information between a pair of random variables A and B is the amount of bits that are required to change from a description of A to a description of B. Formally:
Here p(a,b) is the joint probability of events in A and B and p(a) and p(b) are the marginal (unconditional) probabilities of events in A and B respectively.

Borrowing from the future

On a recent cafeteria chat with my colleagues the subject came to how the current fiscal crisis is fundamentally one of futures trading, and not primarily of sub-prime lending.

It led me to recall another cafeteria conversation I had had some years ago with another set of colleagues where we had collectively come up with the theorem on borrowing from the future.

The scene was that we faculty members were entitled to a free cup of tea (on the house) every day at 3:00PM. A cup of tea cost Rs. 2.50 at that time. So one of us came out with the idea that we will instead have a free samosa costing Rs. 5.00 every other day instead of the free cup of tea. One more came up with the suggestion that we club all the days when we don't receive anything and push them to the latter half of the future, so that we can get free samosas on every afternoon in the former half.

And how long is the future? Infinitely long! So, we're going to abstain from the freebies in the latter half of an infinitely long future! :-)

Meta-modeling heuristics

(Acknowledgment: This post has inputs from Sanket of First principles fame.)

When teaching about formal axiomatic systems, I'm usually asked a question something like, "But, how do you find the axioms in the first place?"

What are axioms, you ask?

To take a few steps back, reasoning processes based on logic and deduction are set in an "axiomatic" context. Axioms are the ground truths, based on which we set out to prove or refute theorems within the system. For example, "Given any two points, there can be only one line that passes through both of them" is an axiom of Eucledian geometry.

When proving theorems within an axiomatic system, we don't question the truth of the axioms themselves. As long as the set of axioms are consistent among themselves (i.e. don't contradict one another) it is fine. Axioms are either self-evident or well-known truths, or somethings that are assumed to be true for the context.

But then, the main question becomes very relevant. Can we assume just about anything as an axiom, just as long as it does not contradict with any other axioms? Or should there be some element of objective truth in the axioms?

Technically, we can go with the belief that truth is subjective and we can assume whatever we want as axioms. But then, this is a self-contradicting statement when used in general. Perhaps one can define a wholly abstract system based on an alternate but consistent set of physical laws and prove that (say) pigs can fly. But other than being seen as "intellectual -er- stimulation", such results are generally not accorded a great deal of importance.

Good axiomatic systems are based on axioms that are grounded in reality and encapsulate some element of objective truth. So the question of "how do we find axioms" reduces to "how do we recognize objective truth when we see it?"

The succinct answer is: "wish we knew". This is the question that has perhaps defined humankind's quest throughout history. And I certainly won't claim to have an answer for that!

But even then, it helps to have some kind of thumb rules or heuristics using which, we can be reasonably confident that our assumptions are grounded in reality. So what follows here are some thumb rules that I have found useful at some time or the other. They are by no means exhaustive and by themselves they don't guarantee that they will lead you to true statements. Nevertheless, it is good to have some thumb rules rather than nothing at all. So here goes:

Principle of invariance Any characteristic of a system that is invariant and displays a property of constancy, is a good candidate for a ground truth. Remember how the north star was used as the basis for designing navigation rules by sailors, long ago?

Principle of least bias (maximum entropy) If you have insufficient information about an external entity that may impact your system in one or more ways, choose the least biased explanation about how the impact will be. For instance, suppose you are constructing a tall building and need to protect it from heavy winds. If you know the direction in which strong winds typically blow from, then you can construct the building in such a way that the building only has sharp edges in that direction so that the wind can cut through it. However, if strong winds are erratic in that region and it is impossible to predict the direction in which they can blow from, design your building on the assumption that strong winds can blow from any possible direction.

The least-bias principle is also known as the principle of maximum entropy, because in information theoretic terms, this also represents the statement with the maximum information content possible about the unknown variable.

Principle of conservation (Symmetry) When you have mapped out the inputs and outputs of your system, typically everything else should be conserved. Else there is something like a "memory leak" happening somewhere that may make your system appear to behave strange eventually.

Every debit should have a corresponding credit (if money was not dispensed out of the system) and every buy should have a corresponding sell. So, don't believe an axiom like, "if lot of people are buying shares from others, then the market is bullish." If lot of people are buying shares from others, it also means that a lot of people are selling shares.

Principle of minimum description length (Occam's razor) If the same phenomenon can be described in more than one ways, choose the simplest possible description. An earlier debate some of us had on elevator design is a motivating example. Occam's razor can also be seen as the principle of irreducibility of the axioms. If the axioms can be reduced to something smaller without changing their meaning, then we probably should be using the latter set of axioms.

Extensibility: This is the dual of the above characteristic. The more facts you can explain using a concept, the better it is as an axiom. Extensability can also be termed the principle of generality. If there are two or more theories for a phenomena, and one of them explains far more than the other (correctly of course), then that is the better one. Quantum mechanics is seen as something that supercedes Newtonian mechanics because Quantum mechanics has a theory general enough to explain mechanics in the sub-atomic level as well as (in principle) at macro levels; unlike classical mechanics that described phenomena only at macro levels.

Universality: Many a time, similar phenomena occur in (seemingly) unrelated contexts. Such phenomena are very likely to point to some deeper underlying principle. The power-law distribution is an example of a characteristic that is found in several disparate systems like degree distribution on the web, population distribution across cities, distribution of the sizes of our blood vessels, etc. It is no wonder that the power law has aroused a lot of curiosity and there are various theories (preferential attachment, utility maximization under saturation) about the truth underlying this phenomenon.

Paradoxes and self references

One of the most celebrated paradoxes in set theory is the Russel's paradox. The story behind the paradox and subsequent developments is rather interesting.

Consider a set of the kind S = {a, b, S}. It seems somewhat unusual because S is a set in which S itself is a member. If we expand it, we get S = {a, b, {a, b, {a, b ....}}} leading to an infinite membership chain.

Suppose we want to express the class of sets that don't have this "foundationless" property. Let us call this set as the set of all "proper" sets, that is, sets that don't contain themselves. We can express this set of sets as: X = {x | x is not a member of x}

Now this begs the question whether X is a member of itself. If X is a member of itself, then by the definition of X (set of all sets that don't contain themselves), X should not be a member of itself. If X is not a member of itself, then by the definition of X (set of all sets that don't contain themselves), X should be a member of itself.

This is the famous Russel's paradox. Bertrand Russel was so flustered by this paradox, he went to great lengths to create an axiomatic basis for set theory that prevents the formation of such paradoxical situations. Incidentally, Russel's paradox also dealt a major blow to David Hilbert's grand idea of representing all of mathematics using set theory. Russel showed that it is not possible to represent some parts of set theory itself using set theory, let alone all of mathematics.

Russel and Whitehead then embarked on a major project that introduced the theory of "types" that was finely intertwined with set theory. This they published as a three volume series called "Principia Mathematica." Set theory could not be described without theory of types and vice versa.

Essentially, the gist of this is as follows. A type is basically a property (a predicate logic statement for instance) and an instance is an element having that property. A set, now becomes a collection of instances sharing a given property. Hence if we have a property isPrimeNumber(x), then the set Primes = {x | x \in Z, isPrimeNumber(x)} is the set of all integers for which isPrimeNumber(x) holds.

In most purposes, we can refer to a set and its type interchangeably. But the subtle difference is that, while we can define a property P(x): x does not contain x without any problem, we cannot define the corresponding set X = {x | P(x)} without getting into a paradox.

In the axiomatic system of Principia Mathematica, a set X can only contain elements belonging to a type lower than that of X itself. This leads to a strict hierarchy among sets, where every set is made up of lower level elements and so on. This brings forth the question, what is the lowest of them all? In order to make sets exist, we will then need to have "atomic" types, below which there are no more sets defined.

This axiom is called the "Axiom of Foundation" in set theory, which prohibits an infinite membership chain and decrees that sets ought to end somewhere.

However, the Foundation Axiom is a little over zealous in its restrictions in order to prevent Russel's paradox like situations. Self reference is not necessarily a paradox.

Suppose we mathematically represent the semantics of each sentence with the set of all nouns in them. Then the first sentence of the previous paragraph would be something like: {Foundation Axiom, restrictions, Russel's paradox}.

Now suppose we want to represent the following sentence in set-theoretic form: This sentence is written in English. We see that there are two nouns here, English and "this sentence". Unfortunately, "this sentence" cannot be an element of "this sentence" according to the Foundation Axiom. Similarly, we can't represent a sentence talking about the universe in general.

There are several situations where self reference is not only consistent, but also necessary. A container class in object oriented programming for example, can contain objects of any class including the container class or even its super classes.

Much later, mathematicians saw the need to relax the Axiom of Foundation and so was born the theory of non-wellfounded sets or "Hypersets." Hypersets are based on the Anti-foundation Axiom that allows self references as long as the cycle does not contain a contradiction. A paradox occurs only when there is a cyclic reference evaluating to a contradiction.

Hence the set X = {x | x contains x} is not paradoxical, while X = {x | x does not contain x} is paradoxical.

It is only that the former set is "non-wellfounded". It is like the story where, a boy who is asked where Leela Palace is, replies that it is in front of Manipal Hospital, and gives directions to Manipal Hospital as "opposite Leela Palace." The sentences are mutually consistent, but by themselves, they don't have any information about how to get there -- either to Leela Palace or to Manipal Hospital.

Such mathematical structures, even though they appear as if they are useless, have some important applications and are very powerful constructs to model some classes of natural phenomena. But more on them in some other post, later.