Plan Inheritance

[neuma]

Idea

At its core, MATSim is a co-evolutionary algorithm that repeatedly performs the steps mutation, scoring, and selection. However, what happens during the so-called relaxation process is mostly invisible to the user.

Some questions this proposal tries to answer

• Which strategies prevail in the end?
• Which strategies fail immediately?
• Which strategies are the most robust and produce the most descendants?
• What does the lineage of an agent's choice-set look like?
• How many iterations do we actually need until the choice-set of most agents only produce inferior short-lived descendants?

At the end of a MATSim run, the following record is available for analysis for each plan ever created.

• agentId: Id of the agent the plan belongs to
• planId: Globally unique plan id
• ancestorId: NONE for plans read initially from file or the planId of the plan from which this plan had been mutated
• mutatedBy: INITIAL for plans read initially from file or the name of the PlanStrategy that altered and thus created this plan
• iterationCreated: Iteration in which the plan had been added to the choice-set of the agent
• iterationRemoved: Iteration in which the plan had been removed from the choice-set of the agent
• iterationsSelected: List of iterations in which this plan had been the selected plan.

Further data like executed scores could be added in a later implementation.

Current situation

In MATSim, each agent has a choice-set of n plans. The choice-set is altered by PlanStrategies in two steps

1. The PlanSelector of a PlanStrategy chooses one plan of the choice-set and marks it as the new selected plan.
2. [Optional] The PlanStrategy may apply PlanStrategyModules to a deep-copy of the then selected plan. Each PlanStrategyModule alters/mutates the plan, e.g. the transport mode of a leg. Eventually, the mutated plan becomes the new selected plan for the current iteration.

This loop is performed at the start of each iteration during the Replanning phase. Each mutation of a plan is a candidate for further mutations in upcoming iterations.

The selected plan of the final iteration is considered the outcome of the MATSim relaxation process.

Implementation Proposal

Once the GenericPlanStrategyImpl mutates a plan during the optional step 2, the then selected plan adds/overrides two new attributes

• planMutator: The name of the PlanStrategy - most likely the result of GenericPlanStrategyImpl.toString()
• iterationCreated: The current iteration as derived from the GenericPlanStrategyImpl.replanningContext

The actual book-keeping is done by a second component - the PlanInheritanceModule. Implemented as BeforeMobsimListener and ShutdownListener it performs the following actions

During BeforeMobsim: Iterate over the choice-set (plans) of each agent

• planMutator == null ? Set planMutator to INITIAL and set iterationCreated to the current one
• iterationCreated == current iteration ? It's a new plan created in this iteration
  • Create new internal record
  • Save agentId in the record
  • Create globally unique planId and save it in the record
  • Save current plan attribute planId as ancestorId in record - this may be not set in case it is an INITIAL plan
  • Override plan attribute planId with the newly created planId of the record
• plan isSelected ? Add current iteration number to the corresponding plan record as growing list of iterationsSelected.

During BeforeMobsim: Iterate over all plan records

• Record refers to plan that is not part of the choice-set of an agent ? Plan got deleted
  • Save iterationRemoved in record
  • Write record to file
  • Remove record

During Shutdown

• Finalize all remaining records
• Write all remaining records to file

Optionally, during shutdown, the PlanInheritanceModule may read all records from file and perform some basic analysis. For instance, the module could create a file indicating for each iteration the share of PlanStrategies among the selected plans of that iteration.

Further more complex analysis should be implemented as post-process.

[neuma]

Just opened a PR (matsim-vsp/matsim-python-tools#23) with basic support for visually inspecting the plan inheritance records.

@rakow Pulling you in here, because I cannot add you as reviewer to the PR.