Experiments with planning and markets in multiagent systems

Naveenkumar Muguda, Peter R. Wurman, R. Michael YoungSIGecom Exch 2004 · DOI

TL;DR

This paper explores how mobile agents can help users navigate complex environments with limited resources by enabling them to plan activities and trade reservations in a marketplace. They demonstrate that allowing agents to trade reservations significantly increases social welfare, especially when combined with better planning horizons and information.

What Problem Does This Paper Address?

The proliferation of mobile, networked computing devices presents an opportunity to create sophisticated applications that assist users in navigating real-world environments. These environments, such as amusement parks, hospitals, or restaurants, often have limited resources (e.g., ride capacity, appointment slots) and can lead to congestion and long wait times. While traditional solutions like physical layout optimization or reservation systems exist, they often lack the flexibility and information needed for users to truly individualize their experience. This paper addresses the challenge of improving user experience and resource allocation in such environments by equipping mobile agents with planning capabilities and the ability to participate in a reservation marketplace.

Methods

The authors model the environment as a connected graph where nodes represent activities and edges represent walkways. Agents are equipped with mobile devices and software assistants that help them plan itineraries. The core enhancements introduced are:

  • Tradable Reservations: Agents can buy and sell reservations for specific activities at specific times in an electronic marketplace. This allows for dynamic adjustment of plans based on changing user preferences or environmental conditions.
  • Marketplace Mechanism: The marketplace uses a k-double auction (k=1/2) where agents bid truthfully. The system uses Mth and (M+1)st price rules to determine ask and bid quotes, aiming for equilibrium. To handle convergence failures, they introduce a bias to the price quotes.
  • Planning Algorithm: Agents use a finite horizon planning algorithm with beam search to enumerate and evaluate feasible plans based on their expected utility. They consider plans of varying lengths and prioritize plans with reservations over those involving waiting.
  • Agent Types: The study considers different agent types:
  • Clairvoyant Agents: Have complete information about the environment, including queue lengths at all nodes.
  • Myopic Agents with Maps: Can see their current location and directly connected neighbors' queue lengths.
  • Myopic Agents without Maps: Can only see their current location.

Datasets

Not discussed in the paper. The authors describe a simulated environment with 10 nodes and 100 agents over 100 time slots.

Key Insights and Ideas

  • The Power of Tradable Reservations: The most striking insight is how much social welfare increases when agents can trade reservations. This highlights the efficiency gains from allowing agents to dynamically reallocate scarce resources based on their true valuations.
  • Planning Horizon Matters (with caveats): For more informed agents (clairvoyant and myopic with maps), increasing the planning horizon generally leads to higher social welfare. However, for myopic agents without maps, longer horizons can be detrimental, as they make plans based on incomplete information and frequently abandon them.
  • Information is Key, But Not Always Sufficient: While clairvoyance provides a benefit, the difference between clairvoyant agents and myopic agents with maps is not as large as one might expect. This suggests that detailed queue information for distant nodes might not be as predictive as initially thought, especially when combined with reservation trading.
  • Reservations Smooth Out Queues: The introduction of reservations demonstrably reduces the variance in queue sizes, suggesting a "smoothing" effect that leads to more predictable wait times.

Key Results

  • Social Welfare Gains: Figures 3 and 4 show that allowing tradable reservations significantly increases social welfare compared to no reservations or random reservations, particularly for clairvoyant and myopic agents with maps.
  • Planning Horizon Impact: For clairvoyant agents, social welfare increases with planning horizon up to at least 3-4 actions. For myopic agents with maps, similar benefits are observed.
  • Reservable Capacity: Figure 5 indicates that increasing the percentage of reservable capacity generally leads to higher social welfare, as it enables more efficient resource allocation through the marketplace.
  • Queue Variance Reduction: Table I shows that in seven out of ten nodes, the variance of queue sizes is reduced when 40% of capacity is reservable compared to no reservations, supporting the hypothesis of a smoothing effect.
  • Number of Trades: Figure 6 illustrates that the number of trades increases with the planning horizon, indicating that agents are more actively using the marketplace to optimize their plans.

Limitations and Future Work

  • Limitations:
    • The study uses a simplified planning algorithm (beam search) with a finite horizon.
  • The marketplace assumes truthful bidding and competitive agents.
  • The model simplifies agent behavior and environment dynamics in certain aspects (e.g., walk pace, random sequencing of agents arriving at a queue simultaneously).
  • The results are often based on single runs, which can explain some variation.
  • Future Work:
    • Exploring better market mechanisms, such as combinatorial exchanges.
  • Developing more advanced planning methods, like partial-order planning.
  • Studying the system's ability to accommodate plan deviations when users develop new interests.
  • Incorporating a traditional AI planner into the agent-human interaction model.

Summary updated

BibTeX
@article{muguda2004experiments,
  author = {Naveenkumar Muguda and Peter R. Wurman and R. Michael Young},
  title = {{Experiments with planning and markets in multiagent systems}},
  journal = {SIGecom Exch.},
  year = {2004},
  doi = {10.1145/1120694.1120699},
}
Figure