We theoretically study the transport properties of self-pr opelled particles on complex structures, such as motor proteins on filament networks. A general master equation formalism is developed to investigate the persistent motion of individual random w alkers, which enables us to identify the contributions of key parameters: the motor processivity, a nd the anisotropy and heterogeneity of the underlying network. We prove the existence of different dyna mical regimes of anomalous motion, and that the crossover times between these regimes as well as the asymptotic diffusion coefficient can be increased by several orders of magnitude within biologic ally relevant control parameter ranges. In terms of motion in continuous space, the interplay betwee n stepping strategy and persistency of the walker is established as a source of anomalous diffusion a t short and intermediate time scales which has not been considered so far.