An automated grid-based storage and retrieval system includes a framework structure, a plurality of storage containers, a container handling vehicle, and a control system. The framework structure includes upright members and a rail system including a grid of horizontal rails provided at upper ends of the upright members. The framework structure defines a storage volume comprising storage columns arranged adjacent one another below the horizontal rails, the grid defining a plurality of grid positions. The plurality of storage containers are stacked on top of one another in the storage columns to form a plurality of stacks in the storage columns. The container handling vehicle includes a lifting device which can be lowered from the container handling vehicle for picking up a storage container. The control system includes records of, for each grid position including a stack of storage containers, a grid coordinate and a level of the storage containers in the stack of the storage column corresponding to that grid position. A method for determining a position of a container handling vehicle on a rail system of an automated grid-based storage and retrieval system includes, for at least one grid position, determining a level of the storage containers in the stack by lowering the lifting device of a first container handling vehicle until a storage container is detected at a vertical position by the lifting device; and determining, using the control system, a grid position of the first container handling vehicle through matching the detected vertical position with a record of a grid position having the same level of storage containers in a stack.