Some ways I’ve seen this solved:
Treat a collision as a failure state
Zachtronics games like SpaceChem and Opus Magnum commonly go this route. The player is challenged to create a program that does not lead to a conflict or collision, and causing one immediately halts execution. The player can then observe the problem, modify the program/machine to avoid it, and re-run the execution from scratch.
An alternative version of this is to self-destruct robots that are in conflict, or turn them into permanent obstacles, but then allow the rest of the execution to continue if it can, rather than treating it as automatic failure. So there may be times when it makes sense to “sacrifice” robots this way, ending their execution while the rest of the distributed program marches on.
Assign “right of way”
You can introduce a simple rule that if two (or more) robots’ instructions for a given tick conflict, then one is deterministically given priority to execute, in a way that the player can easily work out which one that is without identifying characteristics on the robot.
One such rule is “The robot furthest to the east has priority. If two robots in the same east-most north-south column are in conflict, then the one furthest to the south has priority”.
For any cluster of interacting robots, one column of them will always be furthest in the “east” direction of your map, and one robot in that column will always be furthest “south”.
The rest of the robots in the conflicting cluster wait, effectively executing a no-op. You can decide whether they continue trying to execute the same instruction on the next tick, effectively delaying their program, or if the wait causes the instruction to be skipped and they resume at the next instruction after the conflict.
Other robots not in that conflicting cluster still execute their actions simultaneously, so you’re not limited to only one robot moving at a time, which you’d raised as an issue with one of the potential solutions you identified.
Sub-step in a predictable order
You could also allow all robots to act, but have them execute their actions consecutively within the tick rather than simultaneously when there’s a conflict.
You’d use a rule similar to the right of way rule to assign an order of execution, like proceeding west to east, north to south. So the west-most robot on the north-most row of the conflict acts first, then the next one acts (possibly pushing the earlier one out of the way or destroying it) etc.
(This is equivalent to Ryan1729’s suggestion in the comments)
Conflict = wait
You could also choose to treat a conflict as “no move”. The robots detect that they cannot all execute their action this turn, and the conflicting robots wait a tick instead to see if they can continue executing next frame.
(This is equivalent to Zibelas’s proposal to execute the conflicting moves, then rebound and undo them, politely saying “after you”)
Here you’re hoping that another robot not in conflict, or some other change in the map like a moving conveyor/cycling door, results in a new state next tick that can resolve the conflict for at least one of the robots, giving them a chance to recover and continue. If the player has not arranged things so that the conflict is recoverable in this way, then this becomes a deadlock, similar to the “obstacle” variant of the failure state approach described above.
As with the “right of way” approach, you can decide if the stalled robots re-try the same instruction on the next tick, or skip it and advance to the next instruction instead.
When there is a conflict, all conflicting robots immediately skip the conflicting instruction and try the next one. This might produce a new conflict, causing a subset of those robots to skip forward again.
You’d want to introduce a maximum skip depth, or detect when you’ve looped back around to the original conflict to prevent an infinite loop when trying to advance a single tick. If you exceed such a limit or discover such a loop, then you can fall back on any of the approaches above.
When two or more robots enter the same space, they stack! You can use a rule like the “sub-step” approach to decide the order in which they stack and which robot ends up on the bottom/on top.
Just what a stack means, you can determine:
Robots that get driven over are destroyed, and only the robot at the top of the stack remains to continue executing its program next tick.
Stacked robots continue executing their programs, and can be carried along with robots under them if they stay still, or can drive off the stack to un-stack themselves if they move.
Stacked robots’ programs are paused until an outside force un-stacks them (like the robot at the base of the stack driving under a bridge or past a magnet)
Stacked robots merge, making the robot at the bottom of the stack more powerful (eg. able to push heavier objects or resist being pushed because it’s heavier)
(The mobile puzzle game Trainyard implements a clever version of this that I’ll avoid spoiling completely here. 😉)