Framework Design

The Core: Agents and Plans

The framework models the travel behavior of a population of people living in a given geographical region (e.g. town or metropolitan area) as they go about their lives during a certain, often repeated period. The arguably most typical example is a 24-hour weekday, but also other days (such as Sundays) or longer periods (such as complete weeks) can be modeled as long as there is some repetition from one period to the next, i.e. as long as there is something ``typical'' about the period.

During that period the people carry out activities, such as sleeping, working, shopping, eating, etc., at various locations in the region, and utilize the transportation system of that region to travel between activities at different locations. Thus, their activities motivate their travel choices. Also, the limitations caused by the transportation system, such as limited accessibility or congestion, affect their activity choices.

The framework represents each person as an individual entity, called an agent. Each agent makes independent decisions about which activities to perform during the day, where and when to perform them, and what travel modes and routes to take to travel between activities. In our system, each individual agent is represented as a simplified classifier system (20): Each agent has a collection of plans; each plan has a score which is updated after the plan was used; and the choice between plans is done according to their score. The main simplification when compared to a classifier system is that, at this point, our plans are not conditional on the environment. See for example Fig. 2.

Figure 2: Example of information contained in the framework. It keeps all information contained within the agents' plans, with the addition of scores and other bookkeeping information.

5#1

Specifically, a plan contains the agent's intended schedule of activities for the day, and the travel legs connecting the activities. An activity schedule specifies the following information for each activity:

• type: what the agent wants to do (e.g. home, work, shopping, leisure)

• location: x/y-coordinates within the simulated region and/or the network link id (i.e. street)

• timing information: how much time the agent wants to spend at the activity after arriving at its location, and/or absolute ending time of the activity. More detail of this is discussed in Sec. 2.3.

An plan also contains leg information for each pair of consecutive activities. Each leg contains the following information:

• mode: what type of transportation to use

• travel time: estimated duration of trip

• departure time: estimate of what time the trip will begin

• route (certain modes only): the list of network nodes to traverse to get from the previous activity to the next

• (other mode-specific information)

The entity containing all agents' plans is called the agent database. Prototypes of the agent database can be found in (28,29) and in (32). Nagel (28,29) describes a system where agents remember individual scores for different plans, but the plans were the same for different agents and the implementation was for demonstration purposes only. Raney and Nagel (32) describe prototypes of the implementation also described in this paper, but concentrate on a completely different version. That version was not general enough to go beyond dynamic traffic assignment.

Iterations

Above, it was stated that a plan's score is updated after the plan is used. This corresponds to the dichotomy between the mental and a physical layer mentioned earlier. For a single agent, this simply means that the agent keeps repeating the following steps:

1. Select a plan.

2. Execute it and record the performance.

3. Update the score of the plan based on the performance.

In addition, from time to time plans that have a low score are replaced by new plans (see Sec. 2.4). Note that ``execution of a plan'' means that it is submitted to the physical layer for execution. In our case, the physical layer is the mobility simulation. For a multi-agent system, one has in addition that all agents learn simultaneously. This means that a score for a plan is not necessarily stable over the iterations; in consequence, an agent needs to re-evaluate previously bad plans from time to time in order to check if the scores have improved.

The above is a generic design that should work for arbitrary multi-agent simulations. Some remarks are in order:

• It is important to have separate representations of the mental/internal and the physical/external processes. Sometimes, for example in robosoccer (e.g. 26), it is possible that the physical layer is a real-world system, and then part of the challenge is to formulate plans such that they can indeed successfully execute in the physical world. For transportation simulations, a true physical model world will in general not be possible; instead, there will be a simulation of the physical world. However, plans should be designed in a way that they could also execute in the real world.

• The execution of the plan in the physical system can also be seen as interaction of the agent with its external environment and other agents, collecting ``sensory'' input about its experiences, which it then uses to update its mental state (i.e. learn).

• Inside the framework, it would be possible to make plans conditional. For example, there could be a separate plan to follow if the agent got delayed on the way to work. Activity durations (Sec. 2.3) are a (small) example of conditional behavior.

• A plan can be seen as a simple strategy from game theory. For a Nash equilibrium in game theory, an agent attempts to find a strategy that he/she cannot unilaterally improve.

• The framework as described so far is best suited for day-to-day (or more generally period-to-period) replanning. It can, however, be extended to within-day replanning. When doing this, one is confronted with some conceptual and some computational problems. These will be discussed in Sec. 6.

Conditional plans and activity durations

Need more about conditional plans as a concept.

Some diligence is necessary in the treatment of activity durations. In principle, a daily plan is entirely defined by the given sequence of activities, the departure time from the first activity, and the durations of all subsequent activities. This can, however, lead to very implausible behavior: An agent can, for example, shop beyond the closing time of the shop, or remain in the movie theater beyond the end of the movie. In principle, an agent should not plan to do this; it may, however, happen because of unexpected delays earlier in the day. Since this is so grossly implausible, a first step toward conditional plans/strategies was implemented in our framework: Both the activity duration and the activity ending time can be specified, and the ending time takes priority over the duration if the agent's arrival time plus the duration would cause the agent to stay past the ending time. For example, say an agent wants to shop for 30 minutes starting at 17:30, knowing the selected shop closes at 18:00 (specified as the end time of the activity). If the agent arrives late to the shop, at say 17:45, the 30 minute duration would put the end of the activity at 18:15, which is after the ending time. In this case the ending time takes precedence and the agent departs at 18:00 instead. However, if the agent arrives early, at say 17:15, it still stays for 30 minutes and leaves at 17:45 instead of waiting until 18:00.

There is in fact a similar problem with the start of an activity: Assume that a shop opens at 8am, and the agent wants to arrive exactly at 8am and shop for 10 min. Now assume that the agent arrives 15 min early. The plausible thing to do would be to wait the 15 min and then shop for 10 min. Our current implementation will, however, let the agent wait for 10 min and then let him travel to the next activity location. This nonsensical behavior will probably need to be modified in future versions. maybe in final version of this paper??

Generation of strategies/plans

The concept as described so far mostly discusses how agents maintain and use a larger number of plans; there is little discussion of how plans are generated. This is intentional since the precise methods of how strategies are generated does not matter to the overall design. One can for example use constructive algorithms (which construct plans from scratch), mutation (which locally modifies existing plans), crossover (which generates new plans by combining existing ones), etc. In particular, one can use externally existing programs that use the right type of input and generate the right type of output. The only two conceptual requirements are:

• The external module needs to ``think'' in terms of agents. For example, an external route generation module needs to generate a path for a specific agent between two locations, rather than, say, a shortest path tree.

• There needs to be some commonality between what the external module attempts to achieve, and how the scoring is done by the agent database. The system will work as long as some of the plans generated by external modules are ``good'' in the sense of the scoring function of the agent database. This is a considerably weaker design requirement for external modules than TRANSIMS has, where all of the plans generated by external modules need to be ``good''. This is necessary in TRANSIMS because any previous ``good'' (or ``bad'') plan an agent knows about is overwritten by the new plan generated by the module.

Scores

The agent database needs a scoring function in order to give scores to plans that were executed. The primary candidate for the scoring function is the traditional utility function, but any plausible scoring function, for example one using aspect theory (e.g. ), can be used. An example of a utility-based scoring function will be presented in Sec. 4.7. As mentioned before, there needs to be some overlap between what the external modules compute and what the scoring function optimizes.