Same input file, different answer

[Charlie Thornton]

We found a bug in the beta version that jumped to the top of the "things to do before the next beta release" list.

Two simulator runs on the same input file can give two different answers.  Part of our design philosophy in Pathfinder was to make the simulator completely deterministic - no random numbers - so that one input file would give exactly 1 simulation.  If nothing else, it makes it easier to reproduce bugs.  But it also prevents us from using random numbers to create behavior when we can do a better job with rules (that might look random, but aren't).

When you run a simulation in Pathfinder, it creates a TXT file that is actually an input file for the simulator.  The user interface allows you to create probability distributions of things like response (initial delay) time, speed, and size but these numbers are all calculated and etched in stone before the actual simulator starts up.  When you run the simulator manually on the TXT input file, you should always get the same answer.

There are a number of things that might be causing it - an ordering issue from a random-backed collection (e.g. hash table) is at the top of the list.  We'll figure it out.

We found this while trying to reproduce a simulation where an occupant was getting stuck.  Evidently, people are still sometimes getting stuck in reactive steering mode.  It's becoming rarer and rarer though.  I think we're going to get the stuck thing figured out before too long.

We're hoping to have a new version out in a few weeks that addresses this and some of the other issues that testers have noticed.

- Charlie

[Charlie Thornton]

Also, special thanks to Joeri Wilms at Aeolus Consulting for sending us the Pathfinder model this arose from.

- Charlie

[johnni]

Hi all,
If using the model in reactive steering mode I would have assumed that even without random numbers each run would produce a different answer but within a reasonable margin.  I have read somewhere that evacuation models will produce different answers if they go beyond simple movement behaviours. Also, I have run some models where the agent was stuck but in a rerun it was not.  Is this occurring because the steering algorithm is part of the emergent and adaptive behavior family? 

Best Regards John

[Charlie Thornton]

The nice thing about being in the programming business, is that the computers do exactly what we tell them to do.  Even our random numbers aren't really random - they just follow a systematic progression based on a particular starting point.  Emergent and adaptive behaviors (when simulated on a computer) are totally predetermined based on the inputs.  Our problem here was that we had a storage data structure (a hash table that stored the list of boundary edges) using random numbers with an unknown starting point.

Most of the behavior-based simulators out there do give different answers if you run them multiple times.  I believe Steps can specify the random seed, but I don't know how effective that is in forcing the simulation to always come out the same.  The designers do this for a number of reasons.  Usually the one I hear advertised is to enable you to run the simulation 100 times and do a sort of monte-carlo analysis of the scenario.  Having worked on a simulator, I can also tell you that it is very tempting to replace actual occupant-decision making AI with random decisions.  For example:

Early on, we were pursuing an approach where our occupants moved toward exits based on the gradient of a pre-calculated flow field.  The solution was very fast and, with some cornering exceptions, worked quite well.  Unfortunately, it looked unnatural.  People followed perfect lines and curves and it just didn't look right.  Our first throught was to perturb their motion with some random numbers and that made it look a lot better, but it still didn't seem quite right.  Also, we had lost control of the occupants!  What if we wanted to introduce family grouping to the perturbed walking motion.  We'd just be building more and more onto this unnatural model.  Instead we shifted gears and started using more and more of this steering-type behavior that originated from an organized AI process within the agent - no external controls.  By swearing off random numbers we avoided a crutch and in the end we have a  decision-making model that more closely resembles the problem.

Another great example is two or more occupants in counter-flow.  If you add a random component to their motion, they'll glance off each other very nicely.  It's more difficult to make them properly dodge around each other using an organized process.

Pathfinder has a rich enough representation of the space that we can get away with a more "natural" decision making model.  Gridded simulations pretty much have to use tricks to work around the grid.

You can still run 100 different simulations with Pathfinder and get different answers.  In the UI, if you distribute speed, size, etc based on distributions the occupant characteristics will be randomized before the input file is generated and the simulator takes over.  But the simulation logic should always be completely deterministic.

I guess the punchline is that when we get this next beta out, if you run the simulation once and the occupants get stuck, they'll always get stuck.  However, it also means that we'll be able to reproduce that case and fix it.  Every time.

- Charlie

[Richard O'Konski]

In regards to agents becoming stuck, this may either be because of the adaptive behaviors or because of a bug we recently found with clipping internal edges.  When running a simulation, we currently keep occupants away from walls by clipping internal triangle edges away from boundaries.  Unfortunately, there was a bug with this edge clipping that made it into the beta just before it was released.  I believe this was the cause of the strange behavior with occupants becoming stuck or repeatedly running into walls.  We have since fixed this bug, but unfortunately, it's been difficult to determine whether it was the cause of the stuck agents because every simulation produced different results (sometimes the agent would be stuck, sometimes not).  So far, through our internal testing, we haven't experienced any more stuck agents.  This fix for the edge clipping will also be in the next beta.

[johnni]

Hi,
Thanks for the reply. My earlier response shows a lack of programming experience.  In my response and thoughts I narrowed my thinking towards Reynold's flocking etc. I think I understand Charlie's response in that the behavior in Pathfinder is emergent but managed at macro level via a hash table? I trust this also assists with model scalability.  Suppose when you think about it the hash or similar table is a logical approach otherwise we would need thousands of simulations to get something that correlates with real evacuation behavior. 

Best regards John

[Charlie Thornton]

John,

I probably made the hash table sound more significant than it really was.  The hash table is irrelevant to the larger (strategic) question of how the simulator works.  It's just a place where we keep stuff that has some nice performance-related properties.  We probably have hundreds of different hash tables, and lists, and other bags of data in the simulator.  We where just using one in a situation where we needed a particular ordering and weren't getting it.  We changed the kind of has table we were using and now everything is okay.

For the larger question of emergent behavior - I like to think about John Conway's game of life.  It's played out on a grid, each cell is either on or off, and there are only 4 rules.  No randomness at all.  From those four rules, you can get all kinds of exciting behaviors out of the cells based on the initial construction.  The Reynolds steering behaviors, in my mind, are the same.  You can create a flocking behavior using only 3 specific rules.  But, there are no random numbers, and the behavior of the flock is completely pre-determined by the initial state of the simulation.

In terms of correlating the simulation to real evacuation behavior, I'm hoping that our simulator uses a rough enough approximation of behavior that the answer it gives you after a single run can be interpreted as an average.  And that if you were to do 100 evacuations with real humans, the average of the real evacuations would look like the simulated evacuation.  Real humans have a super-complex initial state and can do some weird stuff.  In other words: 100 similar evacuations with real humans might have a large standard deviation, but 100 similar Pathfinder simulations should have a small standard deviation.  That's my hope anyway, we haven't done enough V&V work yet for me to make any promises.

- Charlie