  The exploration of interstellar space will require autonomous navigation
systems that do not rely on tracking from the Earth. Here I develop a method to
determine the 3D position and 3D velocity of a spacecraft in deep space using a
star catalogue. As a spacecraft moves away from the Sun, the observed positions
and velocities of the stars will change relative to those in a Earth-based
catalogue due to parallax, aberration, and the Doppler effect. By measuring
just the angular distances between pairs of stars, and comparing these to the
catalogue, we can infer the coordinates of the spacecraft via an iterative
forward-modelling process. I perform simulations with existing star catalogues
to demonstrate the method and to compute its performance. Using 20 stars and a
modest angular distance measurement accuracy of 1", the position and velocity
of the spacecraft can be determined to within 3 au and 2 km/s respectively. If
a measurement accuracy of 1 mas is achievable then the navigation accuracy
increases by a factor of 1000. Using more stars and/or including also onboard
measurements of the stars' radial velocities improves the accuracy further.
