The Logistics System

I wrote a long blog post describing in detail the process of designing the logistics system, but I've copied the most descriptive part to this article.

Overmind has a very developed, general-purpose logistics system which uses a continuous stable matching algorithm to move resources around. There are two entities in the logistics system: requests and transporters. Request are submitted for targets that need a resource supplied or withdrawn (containers, towers, other creeps, even flags where resources are dropped), and transporters are resource-moving creeps. At its core, the logistics system works by trying to symmetrically maximize resource transport rate dq/dt for both transporters and requests: each transporter ranks requests they can respond to by computing the effective resource transfer rate (transport amount / transport time), and each request ranks transporters that could respond to the request symmetrically. A stable matching is generated via Gale-Shapley to assign transporters to requesters.

Computing resource transport rate As you might imagine, calculating effective transport rate is a bit more involved than simply taking (change in resource) / (distance from transporter to request). When requesters submit a request with LogisticsGroup.request() or a withdrawal request with LogisticsGroup.provide(), several values are logged in a request object:

• target: the object that needs resources in/out
• resourceType: the type of resource requested
• amount: the current amount of resources that need to be moved; positive for request() and negative for provide()
• dAmountdt: the approximate rate at which resources accumulate in the target (this is used to adjust the effective request amount based on the distance of each transporter)
• multiplier: an optional factor to multiply effective resources transported to prioritize certain requests
• id: a string identifier for the request; used for matching purposes

To calculate effective transport rate dq/dt, we need to consider multiple possibilities of what to visit on the way to fulfilling the request. For example, an empty transporter going directly to provide resources to an upgradeSite container would have rate = 0, but if it stopped by a “buffer structure” on the way, like storage or a link, it could have a large transport rate. So the transport rate gets defined as the maximum resource change per total trip time over all possible buffer structures B_k that the transporter can visit on the way:

where \Delta q_k is the maximum of (resources/ or capacity in transporter, |request amount|, buffer resource or capacity) and B_0 is defined to be the target, i.e. going directly there without stopping by a buffer on the way. If the transporter is matched to the target, its task is forked to visit the optimal buffer first. This logic is implemented in LogisticsGroup.bufferChoices().

When calculating \Delta q_k and d_{T_i, B_k}, the logistics system needs to compensate for what the transporter and other transporters are doing. To compute \Delta q_k, predictedAmount() adjusts the effective amount for expected resource influx/outflux from the other transporters currently targeting the request target. (The state of the carry at the end of the transporter’s task is calculated with predictedCarry().) To compute the effective distance d_{T_i, B_k}, nextAvailability() returns when a transporter will next be available and where it is expected to be. (My new task manifests were helpful here.) To better illustrate what these functions do, here is one of my colonies (click this for a higher resolution version):

Referencing the image above, even if R_1 is nearly empty, predictedAmount(R1,T1) can be large because it is far away and there is nothing targeting it. However, predictedAmount(R5,T1) would be close to zero because T_4 is targeting R_5. If we wanted the next availability and carry state of T_3 when it finishes what it’s doing, nextAvailability(T3) = [11,upgradingContainer.pos] and predictedCarry(T3) = {energy: 0}.

Putting it all together

Finally, as pseudocode, here is a stripped down version of my new transporter logic. This is shown only for the request() case – provide() is similar but slightly different – and predictedAmount(), predictedCarry(), nextAvailability() aren’t shown, but they do what they sound like. (See TransportOverlord.ts and LogisticsGroup.ts for the complete code.)

function transporterLogic(transporter):
  if transporter has a task:
    execute the task
  else:
    transporter.task = getTask(transporter)

function getTask(transporter):
  let assignment = LogisticsGroup.matching()[transporter]

function LogisticsGroup.matching():
  let tPrefs, rPrefs = {}
  for each transporter:
    tPrefs[transport] = sort requests by dqdt(transport, request)
  for each request:
    rPrefs[request] = sort transporters by dqdt(transport, request)
  let matching = stable matching from GaleShapley(tPrefs, rPrefs)
  return matching // keys: transporters, values: assigned requests

function dqdt(transporter, request):
  // only shown for request() case, provide() is slightly different
  let amount = predictedAmount(transporter, request)
  let carry = predictedCarry(transporter)
  let [ticksUntilFree, newPos] = nextAvailability(transporter)
  let choices = [] // objects containing dq, dt, target
  choices.push({
    dq: min(amount, carry[resourceType]),
    dt: ticksUntilFree + distance(newPos, request.target),
    target: request.target
  })
  for each buffer:
    choices.push({
      dq: min(amount, transporter.carryCapacity, 
              buffer.store[resourceType]),
      dt: ticksUntilFree + distance(newPos, buffer) 
            + distance(buffer, requesttarget),
      target: buffer
    })
  return choice with best dq/dt