Autonomous localisation and mapping requires a vehicle to start in an unknown location in an unknown environment and then to incrementally build a map of landmarks present in this environment while simultaneously using this map to compute absolute vehicle location. The theoretical basis of the solution to this problem, known as Simultaneous Localisation and Mapping (SLAM)problem, is now well understood. Although a number of SLAM implementations have appeared in the recent literature, the need to maintain the knowledge of the relative relationships between all the landmark location estimates contained in the map makes SLAM computationally intractable in implementations containing more than few tens of landmarks. This paper presents a novel method for representing maps of the environ- ment that substantially reduces the computational complexity of the algorithm and improves the data association process. Rather than incorporating every observation directly into the global map of the environment, the Constrained Local Submap Filter (CLSF)described in this paper relies on creating an independent, local submap of the features in the immediate vicinity of the vehicle. This local submap is then periodically fused into the global map of the environment. Only the fusion of the local submap to the global map require signi cant computational e ort and can be scheduled at appropriate intervals to reduce the overall computational burden. The CLSF algorithm aids in the data association problem as the uncertainties of the feature and vehicle estimates in the local frame of reference tend to be comparatively small. Furthermore, it allows data association decisions in the global frame to be deferred until an improved local map of the environment is available.