Down the Rabbit Hole (Mar. 7 '17)

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:

  1. Model the simplest version of a small-rural-town economy as an Activity Network.
  2. See if using Simulated Annealing, agents find reasonable daily routines at all.
  3. 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.
  4. 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!


Discussion on Reddit

Support Citybound on:

Eureka? (Feb 28 '17)

After describing the difficulties I'm facing while trying to come up with a microeconomy model for Citybound in the last update, I got a lot of very interesting responses, probably since this topic is both at the heart of what Citybound will be and very interesting in general to everyone from smart layperson to expert.

Sometimes it seems like there is only one thing missing for everything to fall into place and in my lucky case it was a hint from a friend, encouraging me to look at "planning graphs" from AI research. Since that wasn't directly applicable, my conscious mind initially rejected this idea, but my ever smarter subconsciousness kept cooking it and not much later presented to me a most delicious idea:

The Activity Network

There is already a road network in Citybound and pathfinding is done on it to find the best way from point A to point B. Direct connections (a.k.a. graph edges) between points (a.k.a. graph vertices) have a cost associated with it: the travel time along the connecting piece of road. An optimal path between A and B is thus composed of road pieces / graph edges with the minimum total travel time.

Now, what if roads weren't the only kind of graph edges, but if there also were activity edges? These would usually form a small loop, simply connecting a place (like a bakery) — using an activity (like "buy a pretzel") — back to itself again (since you are still at the bakery after the purchase). The interesting part is now the more complicated benefit + cost of such an activity edge, which would cover several resources: (-0.4 money, -0.5 time, +1.0 pretzel), describing how the carried resources of an agent using this edge are affected.

Making a trip to the bakery to get a pretzel would thus mean traversing the normal road network edges to get to the bakery, doing the pretzel-buying-loop, say, five times, and traverse the road network edges again to get back home.

Now imagine the whole network of a city like this (and at this point I'd love to already have a detailed example picture, but just imagine) and all road and activity edges having a time cost associated with them. In a way, the road edges are also just activity edges using and giving different kind of resources (using time, fuel, giving scenery, ...), they just happen to bring you to places instead of being loops.

The problem of planning your daily life then just becomes the problem of finding the optimal path through this activity network — in particular the path that, by travelling and using activity edges, accumulates exactly the benefits you need to cover your household's needs, while minimizing negative factors such as fuel consumption, unhealthyness of traveled paths (because why not give the road edges more complicated costs as well!), the tiring effect of some activities, ... while also fitting all of the summed time cost into, for example, 16 waking hours.

This alone potentially allows for complex and diverse behaviours like walking through a park after work to a supermarket and finally going home by subway, not only making reasonable use of the closeness of these facilities, but even making it possible for the supermarket owner to understand the benefit of putting his supermarket inbetween a business center and a subway station (for example by simulating the improvement of "daily path" of a couple representative sample people already travelling there).

Impossible?

The straightforward way to introduce new agents to the city would just be to try finding self-sustaining paths from all currently vacant living space.

Unfortunately pathfinding on huge networks (think all the road segments plus all the activities at each place in the network, keeping in mind that there can be hundreds of households in a single high-rise building) is already difficult enough — but once you start to optimize for not just one cost metrics but several, things get really interesting and complicated (there is not really strictly "one optimal path" anymore but a potentially large set of paths that are hard to compare or tradeoff and each just "don't definitely suck more than another path").

Luckliy, like I a lot of my previous post was about, more humanity saves us again. Almost no one starts off as a blank slate, most of us have an existing life which we might try to incrementally improve from time to time and that should be feasible and intuitively implementable on the Activity Network, even in such a detailed setting.

In the context of a citybuilder, the most obvious way to start everything off is with a couple of agents who just spend their whole day in the "neighboring city" point, which offers all the activities they need to survive, but from time to time they check out if they can use some of the activities offered only (or better) in your new small city to improve their lives, and eventually it will make sense for them to move there altogether.

More complicated details

To actually make the picture more complete at least all of the following need to be added to the model (off the top of my head):

  • distinguishing who is the recipient/supplier of which resource benefits/costs during an activity (person buying a pretzel pays with household money to the bakery business, uses personal time, receives one pretzel from bakery storage, ...)
  • having resource preconditions on activity edges (you can only traverse this edge if you "have a car with you" / if you are an adult / if you have at least 0.5 management education / ...)
  • having time of day preconditions on activity edges (work hours, opening hours, public transport schedules)
  • distinguishing between predicted costs while planning (based on estimates, historical traffic data, ...) versus actual costs while doing an activity (slowdown due to concrete cars on a road, waiting for a cashier to have time, ...)

In conclusion, I have a really good feeling about this idea, to the point where I want to start implementing it right away and see how to best optimize it to millions of agents along the way — since it really contains so many challenges combined in novel ways (if I look at current research) that it seems very hard to predict what will actually be slow.

What really convinces me is how easy it is to imagine both problems and their solutions in terms of the Activity Network, that it ties together transport and activities in this amazing way and that it lends itself not only for planning, but also for running the simulation of what happens at each moment and visualising that in many different ways and even debugging everything!

It's scary but super cool and exciting. Let's do this!


Discussion on Reddit

Support Citybound on:

Turns out it's difficult (Feb. 27 '17)

Here's an attempt to be more honest with myself and you: I've been bullshitting myself into thinking that even the first step of implementing economy (in my ambitious sense) will be fairly straightforward. It's not.

I found this powerful abstraction of using chemical-reaction like activities (in which people and businesses convert some resources into other resources) as the basic building block to model all of the economy in a microscopic way. It seems like in theory I could model all of everyday life in a pretty detailed manner with that.

That is good. Feeling happy about this is good. Jumping to the conclusion that after this great inspiration everything will be easy is stupid. Still, I told both you and me that now I'm just "taking a couple days" to "figure out the last details" before I could get going with implementation.

Well turns out the details are really difficult and if I'm really honest with myself, it starts looking like I only figured out the details, but not the mostly everything.

I am humbled and reminded of this:

So in my slight feeling of discomfort I start looking into recent urban microsimulation research if maybe some people tried to do the same - turns out that, yes, others had exactly this idea.

But they were much more specialized in their applications of it, or, when they tried to show its suitability as a tool for modeling a whole economy (like me), they have still been much more humble in their goals for that (for example "food" being the only consumable resource in a very simple world).

Still, I conclude from reading these papers that my general approach is exactly the ideal theoretical way to go about it, that my "difficult parts" are indeed difficult. Others have just been much more careful in approaching them then me in my naïvety.

What is difficult?

I'll try to keep it short: I want to use activities not just to model what people do and what's going on at each moment in the simulation, but also use imagined 'what-if' activities to inform all kinds of high-level decisions, such as:

  • "Is this higher-quality, but further-away school worth commuting to?"
  • "Will my way to work be shorter if I lived here instead?"
  • "Can I produce pretzels at a competetive price and at high enough volumes to make a profit in this place?"

The first example is pretty simple, since it just affects one person which is evalutating one place, but even there, a large number of activities that this person can do at this school have to be evaluated according to different dimensions.

The second one is even worse, since moving will affect a whole household and now you suddenly might have to trade off the shorter way to work with a longer way to kindergarten, noisier roads and less places for social life, affecting multiple household members, for each all kinds of places of interest, each again offering several potential activities to be judged according to several metrics.

The third example is the worst in that the future pretzel-baker has to incorporate the shopping behaviour of all of his potential customers. Who are they even?

When I lay it out like this, the problem seems to be pretty obvious: a horrible combinatorial explosion of imagined activities to be evaluated, for decisions of just a single person or household.

Maybe slightly less clear is the underlying source of the problem (and this is my biggest insight so far, thanks to my research literature): I'm making a mistake by trying to model perfect knowledge and rational, motivated and flexible people.

The hope: more human humans

In reality, people are not always aware of all the choices they have, they might just have heard about a couple other options and only if the best option they know about is much better than what they currently have, they are motivated enough to change something.

Even then, they never fully evaluate each option, but use lots of thinking shortcuts and approximations to make quick judgements.

Even the business owner has to mix exact calculations with gut feeling when evaluating something as unpredictable as a market or as undefinable as a neighborhood.

By trying to model such imprecise decision-processes, I should not only get much more human behaviour in the simulation, but benefit computationally by doing orders of magnitude less comparison work.

EASIER SAID THEN DONE, RIGHT?

So my new most difficult part is thus to somehow write down all of this handwavy gut-feeling intuition as concrete, programmable rules that are not just stupider, but actually make efficient use of being stupid...

The bright future

If I do manage to pull all of that off, I not only have exactly what I wanted (a cool-to watch, detailed, complex and realistic economy), but I also implemented as a proof-of-concept what current research papers only seem to carefully hint at! That would be cool.

What does this mean for our short-term plans? Well, obviously the February-feature-month will be extended, since it was only a concept-month so far, and I will keep you up to date with my progress on untangling this challenge!


Discussion on Reddit

Support Citybound on:

What I did (Feb. 22 '17)

I'm now living for one month in one of the most beautiful cities I know (and that's very tough with St. Petersburg in the race), can you guess which?

Otherwise, I'm still gnawing on some tough problems with the economy design, but my strategy for solving them becomes more and more clear.

  • I wrote down the rural-town scenario which we implicitly converged on in our discussions, as a minimal, but all-edge-case-covering proof of concept for the economy prototype.

  • I decided to not continue to blindly try to invent all the abstract algorithms around economy without any examples

  • So I started writing down everything that I need in the rural-town scenario, starting with resource types today, and continuing tomorrow with activities and household types

  • I also decided to put all of this kind of data into simple text files that are loaded by the game, instead of directly into the code

  • This should make it possible in the ideal case to add new resource types, business types, new activities and even whole new professions including their interactions without having to compile any code! This will hopefully be the first example of really straightforward and easily discoverable moddability!


Discussion on Reddit

Support Citybound on:

What I thought about (Feb. 17 '17)

I'm still a bit in isolation/meditation mode because I would really like to get my attempt at implementing economy as right as possible from the beginning.

I am starting to have the full picture and there are only a couple open questions left that I'm gnawing at, mostly concerning the mechanisms of scheduling people's days, interaction of schedules between family members and how to do long term planning (rescheduling) in a performant way.

Thank's for bearing with me - next week I'll already be in another city and country and I hope to update you again then with something more concrete!


Discussion on Reddit

Support Citybound on:

What I thought about (Feb. 13 & 14 '17)

Pretty chaotic couple of days, but I had time to think through all the economy goals we came up with in the planning livestream, to review all the great discussion around that and to start sketching some solutions.

Here's a rough first gist:

  • Central concepts:
    • Resources
      • raw materials (wood, grain, milk, iron, ...)
      • processed materials (food, gasoline, paper, ...)
      • processed items (TV, car, printer, machine, ...)
      • money
      • intangible/needs (hunger, health, social life, leisure, education)
      • can be subcategories of each other
    • Activities
      • are conversion recipies / "chemical reactions"
      • have specific resource consumption rates on one side of the reaction, and specific resource production rates on the other side
      • can have "catalysts" that make the reaction faster, or can even be stirctly required to do an activity
      • e.g. "Eating" 0.5 food => -1.0 hunger + 0.1 garbage
      • e.g. "Milking Cow Manually" nothing => 1.0 milk + 0.3 hunger; requires: 1.0 cow
      • e.g. "Milking Cow with Machine" nothing => 5.0 milk + 0.3 hunger; requires: 1.0 cow + 1.0 milking machine
      • e.g. "Walking through park" nothing => 0.2 hunger + 1.0 leisure + 2.0 environment
    • People
      • have private resources & needs
      • travel to participate in activities
    • Households
      • e.g. family or business
      • have shared resources, needs & items
      • offer activities based on available resources
      • do short-term planning for emergencies (always) & spontaneous nice-to-haves (if free time is available)
      • do long-term planning: try to achieve some kind of preferred resource rate equilibrium through scheduling recurring routine tasks (work, buy groceries, ...)
    • Buildings
      • house households

I will try to work this out in more detail over the next couple days, probably already capturing some of that in code, which can then be discussed by everyone interested!


Discussion on Reddit

Support Citybound on: