Thursday, May 11, 2006

Behavioral computing and airline loading...

Can distributed and local computing really be more efficient than centralized planning ? In economics of course, we know the answer, but in computing ?

Consider the problem: how to sequence passenger loading on an airplane so as to minimize completion time. In a Wired article by Dave Demerjian (pointer via Virginia Postrel), researchers proposed a "reverse pyramid" method (rear windows and middles before front aisles, roughly speaking) for loading passengers. The article also mentions "WILMA", or "Window-Middle-Aisle" order, and rotating zones (last 5 rows, first 5 rows, and so on), all of which are in use on different airlines.

Southwest however uses a different method, one that many of you are probably familiar with. Passengers are partitioned into three zones. Passengers enter by zone, and they sit wherever they want. According to the article,
...while Southwest's open seating might seem like an invitation for chaos, it actually illustrates a tendency among passengers to self-organize when left to their own devices. "Passengers who are free to sit anywhere usually do a good job staying out of each other's way," he explains. "Without having studied it in detail, I would imagine that an open boarding model is faster than assigned seating."
What we have here, ladies and gentleman, is an example of "Behavioral Computing". Michael Kearns at UPenn is one of the people investigating this space, and as he puts it,
Perhaps the computer science view of this fascinating line of thought can be best summarized as follows: Using relatively local information, distributed human organizations can compute good approximations to the all-pairs shortest paths problem. What other sorts of distributed optimization problems can humans networks solve?
Now this is not computing in the algorithmic sense: no n^2 time algorithms or NP-hardness results. But it reflects a growing interest in the "wisdom of crowds", social networks, and emergence phenomena (heck, even Charlie Eppes is working on 'cognitive emergence'). Kearns, and his students Nick Montfort and Siddharth Suri have some initial behavioral studies on graph coloring problems: there isn't a paper yet as far as I can tell, but I've heard about the results informally.

For those who might be wondering, this is not warmed-over distributed computing. Distributed computing indeed involved local computations, but the entities were slaves, devices that ran specific protocols that led to the desired outcome (leader election is a classic problem of this kind). There is a notion of malicious machines (a device that may have been compromised), and Byzantine agreement is a famous example of the kinds of problems one considers.

But the fundamental difference is that in this notion of behavioral computing, the local agents are not running pre-specified programs. They are often acting in their own interest, or working under some incentive model, ("I want to find the best seat quickly"), and may execute different procedures towards this goal. The key idea is to set up "a system that controls network structure, information conditions, incentives, and a variety of other variables of interest".

Thus, behavioral computing is more like distributed game theory, and fits nicely into the rapidly growing area of computational game theory.

Categories:

5 comments:

  1. This is probably related to the field of "pedestrian dynamics", which models pedestrian behavior in public areas, especially in panic situations . Pedestrians are modeled as goal seeking, and subject to forces both physical and social. In a panicky rush to a room exit, there is a phenomenen of "arching", in which a small ring of people, pushing against other to get out, forms a rough arch, so that none can escape. I suppose this is a Nash, as well as a physical, equilibrium.

    There is also the area of traffic engineering, which also features a distributed set of goal-seeking agents.

    -Ken 

    Posted by Ken Clarkson

    ReplyDelete
  2. "no n^2 time algorithms or NP-hardness results"

    But there are impossibility results for constrained design of distributed game-theoretic environments. We can encounter any and all of the failure models from: distributed comuting (deadlock, etc.), game theory (suboptimal equilibria), complexity theory (hard-to-find equilibria, intractible-to-design optimal game environments), maybe more. What's less clear to me is how much satisfying unification (a la NP-completeness) the hard/impossible problems of this area exhibit, and whether the difficulties can be cleanly and exhaustively described by something like the above list.

    Auction design is among the more well-established problems in this area, and Noam Nisan's and Tuomas Sandholm's work (among others) approach it from interesting CS angles. 

    Posted by Andy D

    ReplyDelete
  3. Andy: that is true. if one postulates certain models of human behaviour (rational agents, limited knowledge agents etc), then one definitely inherits the formal frameworks that you mentioned above.  

    Posted by Suresh

    ReplyDelete
  4. The problem I have with game theory is that it assumes "rational" agents.

    I'm trying to make money off peoples irrationality. And "optimal solutions" and "Nash equilibria" don't always help, because sometimes, but not always, they don't offer any help in exploiting mistakes of the opponent to the fullest potential. It's like "Ok, I've made all I've expected to make in this situation, now I'm going to give up and be a moron."
     

    Posted by Anonymous

    ReplyDelete
  5. Methinks that the number of items of carryon luggage should
    be the prime determinant of seat allocation and boarding time.
    Greedy algorithm that encourages people to travel light so
    that they can board quicker with less hassle and get first
    dibs on good seats. 

    Posted by Moo Fanchu

    ReplyDelete

Disqus for The Geomblog