One of the first robots I tried to make without instructions, back in the RIS days, was an all-terrain autonomous rover. These robots are nice in that they don't have to be too hard to build or program, but they can have many challenges and thinking problems to overcome, and they can stimulate many creative ideas and designs. Although an all-terrain rover should technically be able to traverse any terrain, we're talking about NXT robots, so you might want to limit yourself to inside your house.
Since your robot needs to move around without you controlling it, you'll need to give it the capability to detect and respond to (or not be affected by) potentially problematic situations. Aside from the obvious one of walls and other simple obstacles, these may include:
- Steep dropoffs
- Short overhangs: sometimes a ledge or other object may block the top of your robot instead of the bottom. In this situation, a mechanism for detecting obstacles soley on the ground level would not be sufficient.
- Bumpy ground
- Steep ramps: sometimes the robot might go up a ramp that becomes so steep that the robot falls over. You'd need something that could detect this (for example, a touch sensor in the back that gets pressed if the robot tilts back too far)
- Obstacles in the back or on the sides of the robot: sometimes the robot might back up or turn into an obstacle (perhaps from avoiding an obstacle in the front). You'd need sensors to detect such objects.
One of the greatest difficulties I've found in building these robots is getting around the sensor and motor limitations. There can be so many things the robot needs to detect, but only four sensors and three motors are available per NXT Brick. You could try using multiple Bricks if you have them, or try to give each sensor multiple functions.
One way to make the robot travel is to simply make it move randomly while monitoring for problem situations and responding to them when they appear. If you wanted to go advanced, you might try to make the robot travel to a certain destination through terrain with random obstacles. Another idea would be to give the robot a task, like cleaning a floor, that it could do while moving around and avoiding obstacles.