Is progress possible in an infinite maze?

Inspired by Maze Solving Robot and the related one on code golf SE

Rules

1. You start in a cell in an orthogonal grid of infinite size. Each cell has four edges, and hence, a maximum of four ways to enter or exit it.


2. Every edge in the grid is either a wall or not a wall.


3. You will choose to execute a series of moves, which will consist of 'north', 'south', 'east' and 'west' instructions.


4. If a wall exists in a direction your instruction indicates, the instruction will be skipped.



5. You can assume that there are an infinite number of cells that are accessible from the starting cell; i.e. walls do not box you into some non-infinite subset of cells.

The Challenge
Find the shortest sequence of instructions one can execute, such that no matter the details of the maze, you can guarantee that you don't end up at the same cell you started from, once execution completes.

P.S. I'm not sure such a sequence can exist; if it can't, prove that.

P.P.S. Help me out in tagging this question....Can't find any relevant ones.

Answer

Let's assume such a sequence exists, and fix a working sequence. Clearly, this sequence does not contain an equal number of NORTH and SOUTH directions, otherwise the robot would return to the starting cell in an infinite 1-wide north-south corridor. The same goes for WESTs and EASTs.

Without loss of generality, we can assume there are more NORTHs than SOUTHs and more EASTs than WESTs. Now let's build a maze to test the sequence. Start with the empty plane. First, we are going to build a straight infinite wall stretching from east to west. The latitude of this wall will be important. If there are $a$ NORTH and $b$ SOUTH directions in the sequence, we want this wall to block exactly $(a-b)$ NORTH directions. This can be done by referring to the following statement:

If an infinite south-facing wall that is $y$ cells north from the starting cell absorbs $n$ NORTHs from the sequence, then an infinite south-facing wall $y+1$ cells north from the starting point will block at least $(n-1)$ NORTHs. This is true because once the robot has bumped into the wall for the first time, it is now in front of the wall, and the rest of the sequence will be executed the same way as if the wall were pushed 1 more cell to the north.

An infinite wall directly on the north edge of the starting cell will obviously block at least $(a-b)$ NORTHs. If it blocks more than that, move the wall 1 cell to the north. If it still does, move it 1 cell further again. At some point it will block exactly $(a-b)$ NORTH directions. That will be the final place of this wall.

Then with the same method we build an infinite west-facing wall to annihilate any east-west movement.

The sequence will return to the starting point in this 'maze'. This contradiction shows that there is no sequence capable of making progress in every infinite maze.

EDIT:

As @NeilW pointed out, once we put our south-facing wall in its place, we can completely ignore horizontal movement by building infinite vertical walls on the left and right edge of the starting cell. Of course, they don't even need to be infinite. They just have to be longer than the sequence itself.