Tag Archives: multiagent

New Job

After  spending almost 5 years working in IBM’s Watson and Watson Health groups, I am moving on.

I am extremely pumped to join IBM Research.  This is a dream come true !

We’re beginning work on a project called Cognitive Eldercare.  Our goal is to keep elders in their home (or assisted living facility) as long as possible and prudent.  With the planet’s aging population, there is an absolutely gi-nor-mous market for eldercare solutions, especially those that cognitively integrate many disparate aspects.

My task is to build the key foundational layer called Knowledge Reactor which is a large, Titan, graph database, extended to emit (react to) graph changes by publishing those changes to a Kafka messaging infrastructure.  We’ll also work (play is more accurate) with lots of IoT devices:  sensors, effectors, robots, drones, and who knows what else.

All that would be cool enough.  But the best part, is we’re going to be writing a lot of agents that react to incoming events and graph change events.  So, I’ll get to build more multi agent systems, and extend my PhD research.

Can life get any better?  God is good !

Encouraging Industry Adoption of Multiagent Systems

AAMAS15I just recently attended the AAMAS (2015 conference in Istanbul, Turkey.  One of the key topics I wanted to explore (again), is how to encourage adoption of autonomous agent and multiagent technology by industry practitioners. There were many others who were equally interested in this same topic.

Milind Tambe chaired a very interesting discussion panel on that very topic the first afternoon.  This is not a case theory vs practice.  There was wide agreement that AAMAS is, and should be, focused on both theoretical and practical aspects of these technologies.

Michael Wooldridge said we shouldn’t kid ourselves.  There are built-in incentives throughout the academic system that naturally encourage more theoretical work.  And AAMAS members are unlikely to significantly modify those incentives.

There was also general agreement that AAMAS should encourage more industrial participation.  But Paul Scerri, who has done a quite a bit of practical application, noted that most of the application-oriented papers he’s submitted in past get rejected.  His rejection comments included:

  • need more detail on <blank>:   8 pages in not enough room to cover even a 2nd level of detail on a running system
  • not novel:  practical instantiations of technology seldom include novel elements.  They are primarily trying to combine multiple elements from others into a working whole.
  • No statistical significance: the primary test for most practical applications (particularly first generation ones) is whether they work or not.  Statistical significance is not a critical aspect.
  • Why didn’t you use <blank>:  Again, the goal of most practical applications is to get them to work reasonably well.  Detailed architectural or technology trade-off discussions are secondary.

In short, Paul compared the time and effort he invested into his submitted papers and succinctly concluded

EU(not submit) > EU(submit)

Sarit Kraus talked about the time she did an radio or TV (?) interview about one of her applications.  Afterwards, multiple people came up to her saying “I have a similar problem“.  Some of the problems were similar; some where not that similar, but it at least got a problem-owner talking with a potential problem-solver.  Promoting a variety of MAS applications to the public, in the hopes of eliciting a “similar problem” response, seems like a very effective way to communicate capabilities and encourage more agent adoption.  Therefore, we should spend more time describing example applications, both at AAMAS and through other forums.

I have often been correctly described as more “solution driven” (a solution seeking a problem) rather than “problem driven” (a problem seeking a solution).  But, in technologies that require deep skills, like ours, “solution driven” approaches are likely to be more effective than “problem driven” approaches.

It seems to me, a separate conference or workshop, focused specifically on industrial application, would be beneficial.  The paper reviews should focus on practical aspects, not theoretical ones.  It should be concurrent with AAMAS to encourage cross-pollination between theory and practice.  I know this has been tried before at AAMAS.  We have to figure out how to encourage practitioners to attend.  So … what do practitioners want from AAMAS?  I assert many want tools, techniques and information that they can apply fairly quickly and easily.  Sure, practitioners are probably also on the lookout for a few longer-term, “big ideas”.  But most of the material needs to be as readily accessible and as ready to apply as possible.  For example, downloadable toolkits and sample test datasets.

Just my two cents.  What do you think?

 

Financial Calculus

StochasticCalculusVol1I recently experienced my own “deflate-gate” (today is Super Bowl Sunday).  I’ve always enjoyed mathematics and was a math major in college.  So I confess, I have an (over?) inflated sense of my math skills.  I was shocked to learn there was a whole different kind of calculus that I never knew even existed — stochastic calculus.

So I’ve been reading Steven Shreve’s books on Stochastic Calculus for Finance, volumes 1 and 2.  This topic is certainly not for everyone, but if the topic interests you at all, this is a great introduction.  I tried reading An Introduction to the Mathematics of Financial Derivatives three years ago, but it was just too dense and too poorly described to be of any real use, and I gave up.  Recently, I decided to try again—this time with Shreve’s book.  It is the contrast between these two books that really makes me appreciate the wonderful job Shreve has done explaining this topic.

I’m interested in financial topics generally because of my job of applying IBM’s Watson technology to the financial domain.  Not that there was a pressing need for stochastic calculus in my job, but hey, you never know how a piece of knowledge might be useful until you need it.

One example of an interesting, yet unforeseen connection, is the possibility of applying some of the financial ideas and concepts to multiagent systems.  A financial option between a buyer and a seller is similar to a conditional commitment between a debtor and a creditor.  The seller/debtor is limiting his future actions.  This represents a cost to the seller/debtor and a benefit to the buyer/creditor.  The question I’ve been recently pondering is: can I adapt the financial concepts for pricing a financial option to commitments?

As an aside, even thought Shreve covers many substantial mathematical topics, one of the best things about his books is his writing style.  The prose is amazingly light for a mathematical text.  He frequently puts the material back into context by drawing connections between topics.  This does a LOT to help the reader see where we’ve been, where we currently are, and where we’re headed.  In addition to dissecting the math, I’ve also dissected some of his prose.  There are many elements of his prose I’d like to incorporate into my own writing style.

Sync

SyncMore travel for me and another great book.  This one is Sync: How Order Emerges from Chaos in The Universe, Nature, and Daily Live by Steven Strogatz.

The simplest example,  echoed on the book cover, is how do millions of fireflies synchronize their blinking.  There is no global “blink now” clock.  There is no master firefly orchestrating the performance.  So how do the fireflies end up synchronized?  It’s a simple idea that requires a lot of thought to truly understand.  The problem seems so simple when you first hear it.  I would have probably waved my hands at it, mumbled that the solution probably looked like XYZ, and then moved on. Only when you really try to solve it, do you begin to see the depth and subtly of this particular rat hole.

Strogatz also discusses many other sync problems:  pairs of electrons in superconductors, pacemaker cells in the heart, hints at neurons in the brain, and many others.  I was particularly intrigued by his discussion of the propagation of chemical activation waves in 2 and 3 dimensions.

There are no equations in the book, but Strogatz’s prose is sufficient to give a good taste of the novel mathematics he and others have used to address these problems.  It was a quick read.

As with most books I read, I begin to ponder how I might apply some of its ideas to multiagent systems.  For one, there are multiple ties to social networking (the A is-connected-to B kind; not the Twitter kind).  I also try to re-imagine his waves of chemical activations around a Petri dish transformed into waves of protocol interactions around a social network.

Most of Strogatz’s problems appear to require continuous-space and continuous-time.  Most of my multiagent system problems are simpler, requiring only discrete-space and discrete-time. I’ve developed some “half-vast” (say it out loud) ideas about using a model checker to approach protocol problems with sync-like elements.  I’d introduce some social operators into the model and an expanded CTL-like expression language.  Models would only need to be expanded enough to check the specific properties under consideration.  I’d also need to introduce agent variables that range over a group of agents to express the kinds of properties I have in mind.  The classic CTL temporal operators are strictly time-like, whereas the social operators would be strictly space-like.  Unfortunately, my current ideas could easily cause a massive state space explosion, so I still have work to do.

I so love reading books like Sync:  books that open intellectual doors and expand conceptual horizons.  I expect I’ll be thinking about these ideas for quite some time.

Using Commitments: When Things Go Wrong

SONY DSCThis is the last in my series on commitments, where we look at what happens when debtors don’t satisfy their commitments.

A debtor agent makes a commitment before satisfying the commitment.  In fact, that’s the whole point of using commitments.  It is a way for a debtor to tell others what it will do in the future.  Since debtors are assessed penalties when they fail to satisfy a commitment, they are certainly encouraged to do satisfy. However, bad things can happen between making and satisfying a commitment.

To paraphrase Spock in The Wrath of Khan, “There are two possibilities. They are unable to respond. They are unwilling to respond”First, a debtor may be unable to satisfy all of its commitments.  Toyota had a lot of commitments to deliver automobiles, but when the tsunami hit it, Toyota was no longer able to keep all of those commitments.

Second, event considering the cost of penalties, a debtor may be unwilling to satisfy all of its commitments.  Airlines knowingly overbook flights, creating more commitments than they can possibly keep.  They willing pay the penalties for their broken commitments.  This covers the case where debtors originally intended in good faith to satisfy their commitments but it is no longer profitable to do so, and where debtors made a commitment never intending to satisfy them.  We don’t distinguish between good and bad intentions in our commitment formalism, because it makes little difference and it is often impossible to distinguish anyway.

To model real world situations, we have to allow these messy cases.  We can not require debtors to always satisfy their commitments. The only thing we do require is that debtors must not leave their commitments hanging forever.  If they can’t satisfy a commitment, then then must eventually cancel it.   Commitment cancellation could be triggered by a timeout mechanism.

Using Commitments: Serial Composition

I Promise

I Promise

Last time, we discussed commitment transformations,.  This time we look at a different kind of transformation that captures the idea of a “chain reaction”:  where knocking over a single domino causes a whole chain of dominos to topple.

The basic idea is to combine multiple commitments that form a chain of commitments into a single commitment.  A chain is well-defined when

  • If the first commitment is satisfied, then the second one becomes unconditional
  • If the first 2 commitments satisfied, then the third becomes unconditional
  • If the first N-1 commitments satisfied, then the Nth commitment becomes unconditional

Since we assume debtors typically honor their commitments (I’ll have more to say about this in a future post) then unconditional commitments will typically be satisfied and deliver the consequent to the creditors.  So whenever the first antecedent becomes true (“fires”), a “chain reaction” eventually occurs and the whole chain of commitment consequents eventually become true (“fire”).  The chain reaction may not occur instantly, but if all debtors eventually honor their commitments, the full chain reaction will eventually occur. Further, the result is a commitment from the set of all debtors to the set of all the creditors.

The chain is incrementally constructed using a serial composition operator of two commitments. So let’s define it and get those gorpy details out of the way now. This post requires more notation than previous posts. I try to avoid notation, but here its just the simplest approach.  I’m using the cool MathJax-Latex WordPress plugin to format this material. This should render in most browsers. Let me know if it doesn’t render well in your browser.

Serial Composition Operator:
When the condition \(C_A.csq \models C_B.ant \) holds, then the serial composition of two commitments, \(C_{\oplus} = C_A \oplus C_B \), is well-defined, and

\(
\begin{align*}
C_{\oplus}.debt & := C_A.debt \cup C_B.debt \\
C_{\oplus}.cred & := C_A.cred \cup C_B.cred \\
C_{\oplus}.ant & := C_A.ant \\
C_{\oplus}.csq & := C_A.csq \land C_B.ant \land C_B.csq
\end{align*}
\)

The well-defined condition simply means that \(C_B.ant\) must be true whenever \(C_A.csq\) is true. So if the first commitment becomes unconditional and is eventually satisfied, then the second comment will also eventually become unconditional.

The transformations in the previous posts never changed the debtors or creditors.  Here, the composite commitment unions the debtors and creditors.  All the debtors are responsible for ensuring the commitment is satisfied. There are different ways to combine responsibilities.  Responsibility can be several (each debtor is responsible for just its portion), joint (each debtor is individually responsible for the entire commitment), or joint and several (the creditors hold one debtor fully responsible, who then pursues other debtors). Serial composition uses several responsibility so that a debtor is never compelled to assume additional responsibilities. The result of serial composition is useful for reasoning about multiple commitments, but all the original commitments must be kept around if we need to determine which specific debtor(s) failed and broke the chain reaction.

Serial composition composes just two commitments, but we can use it repeatedly to combine a chain of multiple commitments. To compose more than two commitments, compose from left to right (the serial composition operator is left associative).

Enough theory, we need an example.  Assume Alice promises to pay Bob some money.  If Alice won’t see Bob today, she can pass the money through Chris, a trusted friend of hers.  (I refer to this as “pay via middle man” or PayViaMM).  There are two commitments.  The first is Alice’s commitment to pay Bob.  The second is Chris’s commitment to pass on any payments he receives (Alice trusts Chris because of this commitment).

C1 = C(Alice, Bob, promise, AlicePays)
C2 
= C(Chris, Alice, AlicePays, ChrisPays)

Serial composition is well-defined because \(AlicePays \models AlicePays\).  Applying the definition above we get the resulting commitment for this chain of two commitments.

\(C1 \oplus C2  := C(\{Alice, Chris\}, \{Alice, Bob\}, promise, AlicePays \land ChrisPays)\)

 Just remember this key idea:  we defined an commitment operator (serial composition) that creates a single commitment that describes the effect of a chain of commitments.  The whole chain is well-defined if firing the first antecedent causes a chain reaction.

Using Commitments: Transformations

I Promise

I Promise

This is another post about using commitments to describe various real-world situations.  For thousands of years, mathematicians have used rules to mechanically transform algebraic equations into simpler and more useful forms.  Similarly, we can define rules to transform agent commitments into simpler and more useful forms.

Let’s extend the pizza example.  Assume Alice commits to Bob that she will give him a pizza and a beer if he either gives her $10 or he helps her move to a new house.

C(Alice, Bob, $10 or helpmove, pizza and beer)

We can break this single commitment down into a set of simpler commitments.  First, Alice will give Bob pizza and beer in either of two situations (an OR operator in the commitment’s antecedent).  This gives us two simpler commitments.

C(Alice, Bob, $10, pizza and beer)
C(Alice, Bob, helpmove, pizza and beer)

We can decompose these down even further, because Alice will give Bob both a pizza and a beer (an AND operator in the commitment’s consequent).  This gives us four commitments

C(Alice, Bob, $10, pizza)
C(Alice, Bob, $10, beer)
C(Alice, Bob, helpmove, pizza)
C(Alice, Bob, helpmove, beer)

Symbolically, we write these commitment transformations like this

C(debt, cred, ant1 OR ant2, csq) = C(debt, cred, ant1, csq),   C(debt, cred, ant2, csq)
C(debt, cred, ant, csq1 AND csq2) = C(debt, cred, ant, csq1),   C(debt, cred, ant, csq2)

In some situations, it is easier to work with these four separate commitments so decomposing a complex commitment makes sense.  In other cases, we might want fewer commitments, and reverse the transformations, merging simpler commitments into more complex commitments.

The key point is once we explicitly describe commitments, we can also define rules to mechanically manipulate them, just like we do with algebraic equations.

Complex Adaptive Systems

ComplexAdaptiveSystemsOn some recent plane trips, I have been reading Complex Adaptive Systems by John H. Miller and Scott E. Page.

The authors discuss a number of topics we all presume we know, but that are seldom explicitly discussed.  For example, they have really nice descriptions of modeling and emergence.  I certainly can’t recall any specific sources for this material.

They talk about “computation as theory”.  Formal mathematical methods  are certainly a valuable means to understand some theories.  But some social systems must have a certain minimal level of complexity before important behavioral phenomena appear.  Those models are just too complex for formal methods.  Computation is the only way forward. This book is all about how to approach building and understanding computational (agent-based) models for social systems.

This book recaps and integrates some material from Wolfram’s A New Kind of Science.  That was also a good readI clearly remember reading that book a decade ago on my backyard patio, bathed in the physical light of the sun and the intellectual light of intriguing ideas.

I also thoroughly enjoyed Scott Page’s (same author) Understanding Complexity lectures which address the same topic, in an abbreviated fashion, in a video format.

The book is a particularly easy read because the examples are simple and clear, and because they use such interesting expressions and metaphors.  (For example, when talking about pixelated pictures, they have this footnote:  “For the romantic among you, assume a stained glass window”.  I loved that).  I also hope to learn a few things about better technical writing by examining the writing style of this book.

 

Using Commitments: Delegating and Assigning

I promise

I Promise

This time we look at two, additional commitment operations: delegate and assign.  Commitments relate debtors (the agents making the commitment and the agents who are responsible for satisfying it) and creditors (the beneficiaries of the commitment).    But sometimes, one agent makes the commitment, but another agent becomes responsible for satisfying it.  At other times, one agent negotiates the benefits of a commitment, but wants to transfer those benefits to another agent.   So after the commitment has been created, we may want to change either the debtors or the creditors or both.

For example, my Manager makes a commitment to his Executive to do some work and give a presentation on the results of the analysis.

CC1 = C(Manager, Executive, receiveRequirements, performTask and givePresentation)

Then he delegates this commitment to me.

CC1.delegate(Scott)

Now, I am on the hook to satisfy the commitment because I’m now the debtor, not my Manager.  Note that the identity of the commitment (CC1) is not changed by these operations; it is still CC1 even after being delegated.

CC1 = C(Scott, Executive, receiveRequirements, performTask and givePresentation)

Now let’s say, the original Executive creditor decides that her manager (SeniorExecutive) really needs to see the resulting presentation instead.  So she can assign the commitment, which changes the creditor for commitment CC1.

CC1.assign(SeniorExecutive)
CC1 = C(Scott, SeniorExecutive, receiveRequirements, performTask and givePresentation)

Many papers use the operation delegate to change debtors and assign to change creditors, as I’ve described here.  However, in my work, I use the more generic transfer operation to do either delegate or assign.  This is just a low-level detail, since both have the same effect.

Delegate and assign further demonstrates the flexibility of commitments.  Commitments explicitly capture an important type of relationship between agents; they capture something that debtors should do in the future.

Using Commitments: A Legal Contract

I promise

I Promise

OrderPayShip (the “workhorse“) showed one way to use commitments.  In today’s example, I’m going to show a different commitment pattern, which more directly models a legal contract.

Let’s assume Bob sells cars and Alice wants to buy one.  Expensive items like this (much more expensive than a pizza) often involve an explicit legal contract.  In this case, Alice and Bob want binding signatures on a legal contract.  We still need two commitments: one from Alice to Bob and one from Bob to Alice.  The trick is to make both commitments become active exactly when BOTH Alice and Bob have signed the contract.  We can model this legal contract as

C(Alice, Bob,  AliceSigns and BobSigns,  AlicePays)
C(Bob, Alice, AliceSigns and BobSigns, BobGivesKey)

Both commitments SIMULTANEOUSLY become unconditional only after both Alice and Bob sign the contract.  Then both parties have to satisfy their individual commitments.

The Workhorse pattern involved only two agent actions:  pay and ship.  What happens when each agent must perform lots of actions?   The legal contract pattern enables you to collect all of a single agent’s commitments to others into a single commitment.  So a more complex example, where Bob provides continuing service to keep Alice’s car running, might look like this

C(Alice, Bob,  AliceSigns and BobSigns,  AlicePays and AliceBuysGas and AliceMaintains)
C(Bob, Alice, AliceSigns and BobSigns, BobGivesKey and BobServices and BobRepairs)

The difference between Workhorse and Legal Contract is more style than substance.  This means you can approach problems from multiple directions.