Down the Rabbit Hole
→ Discussion on /r/Citybound
Just a small update on my quite intense thinking process: since my last update where I described my Activity Network idea, I spent hours and hours reading research literature for inspiration.
As a rough approximation: I have 78 .pdfs in my browser history with relevant URLs, each of which I at least skimmed, including a long survey about the state-of-the-art of the whole research field which I read large parts of.
My conclusions so far:
- What I'm trying to do for each economy agent is strongly related to what is called the "Orienteering Problem" in research (Choosing a route between places to visit, each with differing rewards, given a limited time budget)
- More precisely, it's probably a MOTDAOPTW ("Multiobjective Time-dependent Arc Orienteering Problem with Time Windows") ... if not worse.
- Why does that sound like I'm diagnosing an illness?
- Solving this kind of problem just once (to find one route) is already NP-hard and requires on the order of seconds of CPU time
- I'm fucked!
This is what I'm betting on as a start:
- A semi-random exploration process through the Activity Network (using some form of Simulated Annealing) for each agent, both to generate survivable initial daily routines and to find improvements to them.
- This combines blind guesses ("creativity") with increasingly educated guesses ("reason") to make intelligent lifestyle choices in any given city economy environment and to reevaluate them once conditions change.
These are my next steps in particular:
- Model the simplest version of a small-rural-town economy as an Activity Network.
- See if using Simulated Annealing, agents find reasonable daily routines at all.
- Figure out which parts exactly are slow (i.e. where are completely stupid choices explored) and try to guide the exploration process with as many "common-sense" heuristics as possible.
- Optimize the hell out of it.
Hopefully after that, at least a path towards millions of detailed, smart agents is clear - which is still my goal!
Let me know what you think and whish me luck!