Simulating robotic swarm

Question

I am playing around with swarm robotics and trying to figure out a way to simulate it. Here is my dilemma:

I am trying to simulate thousands of agents that will asynchronously communicate with local neighbors to determine an action so a global behavior can be achieved without a centralized logic center. The initial solution to simulate this seems pretty straightforward - each agent is a thread, however, I can't spawn thousands of threads. I also looked into the actor-model framework, but that also does not work since it's single-threaded so I lose the ability for it to be async and whenever an agent is waiting for a signal, it will be thread blocking so other agents will never be able to execute and logic. Any direction will help. Happy to add any clarification. Below is an example of threading. I am trying to create a swarm of 20,000 agents however I cannot create 20,000 threads. I need each agent to run in parallel as that is how it would work with real hardware.

main.py

n = 20000
for i in range(n):
    agent = Agent()
    agent.start()

# Additional logic to start sending and receiving messages between agents.

agent.py

class Agent(Thread):
    def __init__(self):
        ...

    def send_message_to_neighbor(self):
        pass

    def receive_message(self, message):
        pass

error

error: can't start new thread

Answer 1

This is an ideal use case for async/await.

Your simulated agents will spend nearly all their time waiting for something. It doesn't take a whole thread, with its stack size and address space used and all that, just to wait. Using the async formalism, a small number of threads can service a large number of async agents. At any moment, only a small number of agents will have something to do, and once they do it they will go back to waiting.

A lower-tech, lower-elegance alternative is to frequently poll each agent, giving it a chance to discover whether it has anything to do yet. In this arrangement, you need to explicitly code the agent to return to the caller ASAP so it can get on with polling the next. This also means that any state it needs to preserve from one poll to the next -- even tiny things like loop counters -- must be stored in some instance.

With async/await, the system automagically takes care of that for you. Unfortunately, in my experience, it also leaves you on your own to wrap your mind around this kind of concurrency.

As an aside: in your simulation, even if you use a polling loop, try to manage simulated time abstractly, separated from real time (but with a way to tie them together). This can radically speed up rerunning flocking algorithms, for instance.

—edited to summarize comments and further chat into the answer—

Q: Won't async/await block the main application thread?

A: Well, some thread needs to run the async event loop. Just like a GUI program needs some loop to handle mouse and keyboard events, and whatever other work you would put into the main thread. If threads are scarce, or thread hopping is constrained, the challenge is to field both kinds of events when only one loop is "in charge". Typically the APIs have a way to drain all pending events of one kind but without waiting for more. You would run that once each pass of the other kind of loop.

A: I put a proof of concept in github.com/rbryan13/swarmbots

Q: I'm still trying to understand asyncio in terms of thread blocking. I am coming from javascript and trying to relate it to async/await. In JS async/await will block the main thread. Looking at the repo on line 155 when you call asyncio sleep, wouldn't that prevent other Robot class instances from calling their update method?

A: No, it won't, because of the async magic. When a def is marked async, it doesn't return a normal result, but rather a coroutine (or generator, or future, or promise, or something). When it executes an await, it immediately returns a coro (or etc). When the wait's condition is satisfied, the coro's execution picks up right where it left off. Doesn't matter where the await was -- inside a loop, try/except, whatever. While it's awaiting, the coro's execution state gets saved in a system-defined instance, but otherwise it doesn't occupy any system resources -- no stack, no polling.

So we can have thousands of awaits all pending at the same time. Each only occupies a few hundred bytes for the execution state, instead of the tens of thousands that a thread's stack would occupy. Asyncio's scheduler (part of the event loop) keeps track of all the waiters, and resumes execution of each as soon as its condition is satisfied. Whatever thread is running the asyncio event loop is sort of used up doing only that. In the PoC it's asyncio.run() on line 205. But that's OK if all the work gets triggered by something (i.e., awaiting something). If doing actual work takes noticeable time, there's a way to have it dispatch coros to other threads, so you can apply more cores to the task. The PoC didn't bother with that. Sometimes there are thread constraints, like maybe GUI activity has to happen in the main thread. Then you need to get into thread hopping.

Q: However, would this PoC be able to expand given the 2 constraints:

1. Each robot needs to communicate with its neighbor in order to move to a position. If the robot sleeps, how would it be able to communicate with neighbors?
2. Instead of all robots moving to a centroid it would have to move to a defined shape or mesh.

A: You could give each robot an inbox, and it could do something like await inbox.get() asyncio.Queue would serve. If the robot's only behavior is triggered by incoming messages, use those instead of asyncio.sleep. If you need to sleep, or await other things too, use async.wait() with return_when=FIRST_COMPLETED. Or maybe asyncio.as_completed(). Those want a list (actually iterable) of awaitables. Instead of "await foo(); await bar()" use w = [foo(), bar()] and pass that to asyncio.wait or whatever.

Q: One flaw I do see with async/await method is that if I am performing logic inside the update method and logic inside that method requires communication with other Robots, that will not be possible. In order to exit the update method I need information from neighboring robots but I can't get information from neighboring robots until I exit the update method. Thinking about it some more, I could add an await to the outbound request from Robot A to Robot B which would switch the context to Robot B.

A: Exactly. Just as your simulation could run N bots concurrently, each bot could run K tasks concurrently. The bot could have separately concurrent tasks to (a) query neighbors for computing swarming behavior; (b) update its position based on speed, direction, and elapsed time; and (c) respond to queries coming in from its neighbors. Careful handling of task canceling could simplify the various loops by not checking arena.keepRunning.