Complexity Explorer Santa Few Institute

Consider the following system:

You have a 100x100 square checkerboard and there can be at most one checker on any given square at any time.  At each time step one or more checkers randomly appear on squares in the left-most column of the board.  When a checker arrives on the left-most column it is randomly assigned to a destination square on the right-most column (anytime a checker arrives on the right-most column it is removed from the board).  At each time step, a checker can either stay put or move to an adjacent square in any of the four cardinal directions as long as that adjacent square is open at the start of the time step (if more than one checker wants to move to the same square, one is randomly chosen to occupy the square and the others must stay put).  Checkers must make their movement decisions based on a set of local rules (potentially unique to each checker) that only use information about the checker's current position on the board, its destination, and whether squares in a local neighborhood are occupied.  The local neighborhood consists of all squares that could be reached in R steps in the cardinal directions across adjacent checkers (see examples below).          

Neighborhood of size 1:    

Neighborhood of size 2:      

Your challenge is to:

1) Create a compact set of rules that can efficiently move the checkers to their destination.

2) Investigate how the system performs under various conditions, for example, as the number of arriving checkers increases, as the neighborhood size changes, as the destinations become more distributed relative to the location of the arriving checker, as the rules are prone to errors, as squares become unusable, and so on.

3) Suggest real-world applications for your results.

Solution guidelines

• Clearly define useful notions of "efficiently move the checkers"
• Derive a useful set of rules given your notions of efficiency
• Explore the system's performance under interesting conditions like those suggested in (2) above.
• Suggest some real-world applications
• Provide a coherent write up and analysis, no longer than five pages, excluding tables and figures, in PDF format
• Create a clear, concise video description of the challenge and solution, no longer than three minutes, and no larger than 25mb, in mp4 format
• Develop some general theoretical principles of this system
• Suggest related literature
• Suggest future research directions

For general Challenge guidelines please go here: https://www.complexityexplorer.org/challenges/pages/guidelines