Ricochet Robots and interesting game trees

Every Wednesday at work we have a Games Night - people bring along (non-computer) games, we get together, and we play a few. Last Wednesday, someone brought along Ricochet Robots. I wasn't very good at it, but the game intrigues me from a computational point of view.

Essentially, it's a puzzle game. You have a board divided into squares. Each square is either empty or has a target. A target consists of one of four colors and a symbol. Walls are (seemingly) randomly scattered around the board, blocking passage between adjacent squares. There are four robot tokens, in the same colors as the targets, which start off scattered around the board randomly.

There's also a set of tokens, one for each target. One of these is drawn randomly and placed face up in the center of the board. It specifies that the robot of that color must make its way to the target with that color and symbol. Robots move like they're on a skating rink - they can move in any of the 4 cardinal directions, but once moving continue until they hit a wall or another robot. Nobody owns a robot - all 4 robots may be ...