Unmanned aerial vehicles (UAVs) have the potential to make a significant impact in a range of scenarios where it is too risky or too costly to rely on human labour. Fleets of autonomous UAVs, which complete tasks collaboratively while managing their basic flight and related tasks independently, present further opportunities along with research and regulatory challenges. Improvements in UAV construction and components, along with developments in embedded computing hardware, communication mechanisms and sensors which may be mounted on-board a UAV are nearing the point where commercial deployment of fleets of autonomous UAVs will be technically possible. To fulfil this potential, UAVs will need to operate safely and reliably in complex and potentially dynamically changing environments with path-planning, obstacle sensing and collision avoidance paramount. This survey presents an original environment complexity classification, and critically analyses the current state of the art in relation to UAV path-planning approaches. Moreover, it highlights the existing challenges in environment complexity modelling and representation, path-planning approaches, and outlines open research questions together with future directions.