APPROACHES TO THE PROBLEM

We can take many kinds of approaches to the problem. At first sight, it seems a kind of planning or scheduling problem in an artificial intelligence sense. Although determining a plan for an individual user can be executed by planning, social coordination cannot be handled well by conventional planning and scheduling techniques that lack real-time response.

Genetic algorithm (GA) or reinforcement learning works well because of its ability to generating new, flexible plans, but it also lacks real-time response. Stochastic distribution, e.g., CSMA/CD used in Ethernet (IEEE802.3) for packet collision avoidance , works fast, but it cannot generate good plans because it doesn't take the user's intention or preferences into consideration.

Another approach is to introduce some kind of market or auction mechanism by preparing a kind of bulletin board where a part of plan linked to users' intention or preferences is exchanged among users. Market or auction mechanisms reflect an individual user's model and generate good plans faster than planning, GA, and reinforcement learning, but it is slower than stochastic distribution.

To summarize the candidates for social coordination mechanism, each candidate has merits and demerits as follows :

1. Combinatorial Optimization . Coordination problem can be formalized as combinatorial optimization problem (e.g., Lawler et al., 1985) in many cases, which can generally be solved by genetic algorithm (Goldberg, 1989). This approach can give the most optimal solution, but real-time response is difficult.

2. Stochastic Distribution . Stochastically distributing resources among users is a time-efficient approach (e.g., Floyd et al., 2001), which can be analyzed by a queuing network (e.g., Chao et al., 1999). The solutions obtained by this approach usually lack accuracy, i.e. obtained solutions are far from optimal ones.

3. Market Mechanism . Methods based on market mechanism (see Wellman et al., 2001; Prado & Wurman, 2002) can reflect the flexibility of users' motivations and intentions, and it keeps real-time response. Basically, fluctuations are observed in market mechanisms, by which the behavior of the whole system can become unstable.

4. Planning and Scheduling . Conventional AI planning and scheduling (e.g., Miyashita, 2000) are flexible methods that can control spatial and/ or temporal complexity and the accuracy of the solution by using heuristics. Unfortunately, preparing good heuristics for all kinds of problems is nearly impossible .

We are now designing an algorithm for mass user navigation based on the generation, connection, and evaluation of plans, with stochastic distribution and exchange in market and auction mechanism. The basic idea is that, first, we generate element plans for individual users, and then we connect the plans to increase both types of utilities. If congestion occurs in this process, we modify each user's plan by stochastically distributing its elements in the resource place. This algorithm itself seems to work well and fast, but it does not generate good candidates because it does not take the user's intention or preferences into consideration. We then introduce an exchange mechanism, by using a marketlike bulletin board, in order to decrease the number of the applications of stochastic distributions.