Encoding neighborhoods

[DavidNKraemer]

Every agent has an immediate L-infinity neighborhood consisting of 8 adjacent squares. Each square can contain one of three possibilities:

• empty space
• obstacle
• another agent

In the case of another agent, we may sometimes want to know the move they plan on making (if they come up first in the priority queue, this is TBD). There are five possibilities:

• move up
• move left
• move down
• move right
• don't move

The easiest way to represent this neighborhood is to encode it as discrete variables. The following is an example encoding:

Code	State	Code	State
0	Empty space	4	Agent, move left
1	Obstacle	5	Agent, move down
2	Agent, no info	6	Agent, move right
3	Agent, move up	7	Agent, don't move

So that means each square can hold a number between 0 and 7, inclusive. In this framing, an integer vector of length 8 fully describes the neighborhood.

The problem is that integer encoding is well-known to be a bad way to train neural networks and other continuous-parameter models. A common alternative is one-hot encoding, which represents the codes by the vectors [1, 0, ..., 0], [0, 1, ..., 0], ..., [0, 0, ..., 1], where each vector has length 8. This means that our neighborhood is fully described by an 8*8 = 64 length binary vector.

The new problem is that we went from O(n) space for the neighborhood of size n to O(n^2). This may be a difficulty. Any thoughts?

[wessle]

If we're representing the agents' state using a matrix representing the board, neighbor move intentions could be encoded with different values, or, if we represent things with simple images, arrows or colors/shades. This assumes we're using CNNs for our approximators.

In this kind of setup, we could furthermore potentially represent the direction of the goal state, congestion, etc. using similar "visual" cues.

[LoganDGraham]

Three thoughts:

1. Wes' point brings us back to the decision of whether we want to represent agents' locations as either (a) a matrix that encodes the board, or (b) a list (perhaps a dictionary) of local neighborhoods. If we choose (a), then I don't see how a sparse representation is practicable (in contrast to my knee-jerk reaction), for we aren't doing multiplication with these board states. Either (a) or (b) should work, right? These problems would need like a 10,000x10,000 board for the matrices from (a) to be too big, right? Which of these representations would be an easiest starting point?

2. A wild idea: use a color gradient of white-to-black. Each agent's location is shaded with a float between 0 (white) and 1 (black). Whiter shades are when the agent is farther from its destination (manhattan distance, the relevant metric). 1, black, is when the agent is at its destination. If we were to use the representation (a) from above, the matrix's elements would be, say, -1 for empty spaces, and floats in (0,1] representing agents. This might make it more tractable to employ representation (a) while also keeping away from a troublesome categorical representation (e.g., integer i for agent i's location; integer -i for agent i's destination), as David admonished.

3. In the representations of agents' local neighborhoods, is it indeed advantageous for a fixed agent's local neighborhood to distinguish between obstacles and other agents? Regardless of whether we consider problem-statement 1 or 2, it is not clear to me whether distinguishing between obstacles and other agents is necessary or unnecessary.

[LoganDGraham]

Ehhhh. My #2 is a little problematic. Should probably represent agents' destinations directly, not just their distances-to-go...

[LoganDGraham]

Answering my own question (3) from above: Yes, it is most certainly important to distinguish between obstacles and other agents in the distributed state description (i.e., that in which each agent keeps track of his local neighborhood). I've sketched out justification for this on paper.