The adaptation of conventional robots to construction sites is fraught with problems. Most significant of these are in relation to positioning, means of collision avoidance, and appropriate navigation strategy. This paper reviews the different levels of navigational autonomy that are possible and describes the system requirements for each. A taxonomy based on the concept of a Mobility Automation Level (MAL) is proposed. Each level is described and the requirements from a robot design perspective are discussed. Finally, a case study, based on an excavator with autonomously optimised movement, known as LUCIE, is used to illustrate some of the design criteria previously described and discussed.