  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 and aberration. 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 the 20 nearest stars and a modest
angular distance measurement accuracy of 1", the position and velocity of a
spacecraft light years from the Sun moving at relativistic speeds can be
determined to within 3 au and 2 km/s respectively. These accuracies improve
linearly with the measurement accuracy, e.g. with angles measured to 1 mas the
navigation accuracy is 1000 times better. Performance can also be improved
using more stars, or by including onboard measurements of the stars' radial
velocities, as these too are affected by the spacecraft's position and motion.
