FORMALIZATION OF THE PROBLEM: RESOURCE SPACE, PLAN, UTILITY

In this section, we formalize the problem of mass user navigation in order to deal with it by computational methods . The formalization is as follows . The symbol U denotes the set of all users, while u denotes each user, i.e.:

The set T is given as temporal segments in the form of a simple discrete representation of time. The set S is given as spatial segments in the form of a qualitative representation of space, e.g., a region corresponding to the neighborhood of an attraction in a theme park, or a region in which users can access a specific wireless LAN access point (see Kurumatani, 1995; Kurumatani & Nakamura, 1997). Social resource set R is defined as the direct product of the temporal segments and spatial segments. The capacity of resources is represented as a function: cap ( r ): .

A plan is a point sequence in the resource set R along time, where there is no same temporal segment in the resource sequence of any plan. Therefore, a user cannot be in two or more spatial segments at a time. When there is no common temporal segment that belongs to some pair of plans selected from the original ones, more than one plan can be connected to become a longer one, i.e.:

This connection process is mainly used to generate a new candidate of plans from simple short ones. From the viewpoint of search in artificial intelligence, the search space has the complexity of the number of S to the number of T : O ( Plan ) = S ^T , where Plan is the set of all possible plans.

The resource space where plans are generated and verified is shown in Figure 3. The vertical axis shows the time flow represented by temporal segments; the horizontal axis shows the spatial segments. A plan for an individual user is shown as a broken line, and congestion (resource conflict) occurs on the place shown by circles. If the capacity of resources at the place is less than the number of total plans crossing there, congestion occurs at the place in the resource set.

Figure 3: Plans and Congestion in Resource Space

Another important element in the formalization is the utility of plans, which is used to measure their effectiveness for individual users and society. Basically, both of the utilities can be defined arbitrarily to control the reasoning process. In our formalization, as a utility for individuals, we use (1) the linear addition of the evaluation of each resource, and (2) the evaluation of special sequences appearing in the plan. As a utility for society, we use macro-attributes of the society, e.g., degree of congestion, use ratio of resources, environment pollution, and so on. It is difficult to balance two kinds of utilities for individuals and society. The criteria for the balance are deeply connected with the policy of what kind of social coordination we want to realize. For the present, we use linear addition for both types of utilities.