implement RoadWork/RoadBlocking example

[hoechp]

implement RoadWork/RoadBlocking example!

...and try to make sure is works correctly and with acceptable performance!

(see #23)

[hoechp]

It all seems to work, except for a bug with setting attribute values through applying matches:

PatternAttributes have only one 'value' for specifying an attributeMatchExpression - this is String. If attributes are set to String-values, that's ok - but we want to support Boolean, Integer, Long, Double and String as attribute-value. So I have to create an additional attribute in PatternAttributes for values to set, or change the type of the one holding the attributeMatchExpression to Object, which is the option I'll probably implement.

[hoechp]

It seems to run correctly with all rules. But it is very slow. I definately need to look at ways to improve performance of building the reachability graph and/or isomorphism checks and/or pattern matching.

On a minimal version of the map with just 5 pieces of road, it takes 3 seconds on my pc, yielding 192 reachability nodes. With 6 pieces of road, it takes 10 seconds on my pc, yielding 576 reachability nodes. The full example with 11 pieces of road didn't complete the calculation within 1.5h of test. I'll let it run through the night to see how long it will take.

[hoechp]

The original setup did take 2 hours and 20 minutes to complete, yielding 20480 nodes in the reachability graph. I think that's a lot of nodes - my isomorphism checks, rule matching and rule application should all work properly though, so I'm thinking: Was it really the correct and not near correct rules, I've used? In the original RoadworkExample using SDMLib it somewhere says, it should be 4353 'reachable states'.

[hoechp]

Okay, at the very least I had both signals green at the beginning, now my stats are being updated:

• 5 pieces of road (minimal setup) took 2.1 s, yielding 128 nodes
• 6 pieces of road (2 in the middle) took 7.5 s, yielding 408 nodes
• 11 pieces of road (original setup) took 3867.8 s (or 64.5 m), yielding 13568 nodes

[hoechp]

If my rules ain't correct, it must be the signals.

   private void addSignalRuletoGreen1(StoryPage page, ReachabilityGraph reachabilityGraph) {
      MapPO signalControlPO = new MapPO();
      SignalPO signalsPO = signalControlPO.createSignalsPO();
      signalsPO.createPassCondition(false);
      TrackPO trackPO = signalsPO.createTrackPO();
      trackPO.createCarPO();
      signalControlPO.createSignalsPO().hasMatchOtherThen(signalsPO).createPassCondition(false);
      signalControlPO.createCloneOP();
      signalsPO.createPassAssignment(true);
      signalControlPO.setRuleName("signalToGreen");
      reachabilityGraph.addToRules(signalControlPO);
      page.addPattern(signalControlPO, false);
   }

   private void addSignalRuletoRed(StoryPage page, ReachabilityGraph reachabilityGraph) {
      MapPO signalControlPO = new MapPO();
      SignalPO signalsPO = signalControlPO.createSignalsPO();
      signalsPO.createPassCondition(true);
      TrackPO trackPO = signalsPO.createTrackPO();
      trackPO.startNAC().createCarPO().endNAC();
      signalControlPO.createCondition(new Condition<Map>() {
         @Override
         public boolean update(Map m) {
            TrackSet bidirectionaltracks = m.getBidirectionaltracks();
            for (Track track : bidirectionaltracks) {
               if (track.getCar() != null)
                  return false;
            }
            return true;
         }
      });
      signalControlPO.createCloneOP();
      signalsPO.createPassAssignment(false);
      signalControlPO.setRuleName("signalToRed");
      reachabilityGraph.addToRules(signalControlPO);
      page.addPattern(signalControlPO, false);
   }

As far as i understand, the green rule says "If a car is at a red signal, and the other signal is red, too => turn the signal at the car to green". The red rule, I probably implemented wrong. I now think it says "If a signal is green, and there's no car on any bidirectional track/road, turn the signal to red.". Before I had something where the green light would turn red as soon as there's no car on the signal - totally wrong. Also I had an error in the 6-pieces-of-road map...

• [x] fix the rule and run the tests, again!

[hoechp]

new stats:

• 5-roads-map: 1.3s, 80 nodes
• 6-roads-map: 2.6s, 144 nodes
• 11-roads-map: 409.6s (or 6.8m), 4352 nodes

The original example says 4353 and not 4352, though - I'd say "close enough", but I have to wonder, what's the difference...

Also I keep thinking about improving the performance.

[hoechp]

(
7 = 7 non empty west-going middle car states * 1 signal state
+
7 = 7 non empty east-going middle car states * 1 signal state
+
3 = 1 empty middle * 3 signal states
)
*
4 incoming eastern car states
*
4 incoming western car states
*
4 outgoing eastern car states
*
4 outgoing western car states
=
4352

I've just calculated, how many states there could be - and it's just 4352, so I'm quite sure, that my 4352 states and not the stated 4353 are correct.

To further support this: 4353 = 3 * 1451 (prime factorization) - that makes no sense combinatorially

Note: I believe, you could adjust the rules, so one of the signals always is green and the other one is red, this would yield just (7 + 7 + 2) 4 4 4 4 = 4096 nodes and therefore be a bit quicker.

[hoechp]

What I especially like about my way of doing this:

private PatternGraph signalToRedPattern() {
    PatternGraph graph = new PatternGraph("signalToRedPattern");

    PatternNode signalAboutToTurnRed = new PatternNode("#{type} == 'signal' && #{pass}")
            .setPatternAttribute("+", "pass", false);

    PatternNode carAtBidirectionRoad = new PatternNode("#{type} == 'car'").setAction("!=");
    PatternNode easternRoad = new PatternNode("#{type} == 'road'").setAction("!=");
    PatternNode westernRoad = new PatternNode("#{type} == 'road'").setAction("!=");
    PatternNode bidirectionalRoad = new PatternNode("#{type} == 'road'").setAction("!=")
            .addPatternEdge("east", easternRoad)
            .addPatternEdge("west", westernRoad)
            .addPatternEdge("car", carAtBidirectionRoad);

    graph.addPatternNode(signalAboutToTurnRed, carAtBidirectionRoad, 
        easternRoad, westernRoad, bidirectionalRoad);

    return graph; 
}

(my 'signal turns red'-rule)

   private void addSignalRuletoRed(StoryPage page, ReachabilityGraph reachabilityGraph)
   {

      MapPO signalControlPO = new MapPO();

      SignalPO signalsPO = signalControlPO.createSignalsPO();

      signalsPO.createPassCondition(true);

      TrackPO trackPO = signalsPO.createTrackPO();

      trackPO.startNAC().createCarPO().endNAC();

      signalControlPO.createCondition(new Condition<Map>()
      {
         @Override
         public boolean update(Map m)
         {
            TrackSet bidirectionaltracks = m.getBidirectionaltracks();
            for (Track track : bidirectionaltracks)
            {
               if (track.getCar() != null)
                  return false;
            }
            return true;
         }
      });

      signalControlPO.createCloneOP();

      signalsPO.createPassAssignment(false);

      signalControlPO.setRuleName("signalToRed");

      reachabilityGraph.addToRules(signalControlPO);
      page.addPattern(signalControlPO, false);

   }

(the 'signal turns red'-rule in SDMLib)

I think my pattern building is more intuitive