This paper presents the concept of an unmanned robotic team, consisting of an aerial and a ground vehicle, and a power-tethering physical link between them, and proposes a strategy that addresses their collaborative navigation problem. The purpose of such a team is to exploit the technical advantages of differentiated unmanned vehicle classes in an approach that benefits the global navigation objective, but with each agent also directly benefiting from the capabilities of the other at an operational level. This conceptual team aims to address the challenge of prolonged autonomous navigation within environments, for which a limited amount of information is available prior to deployment. To this end, the team works its way through the map, while incrementally exploring and rebuilding the actual environment structure, relying on sampling-based trajectory planning techniques and a 2×2-Dimensional decomposed manifold model of its workspace. A challenging environment model is formulated for simulation purposes of the proposed approach, and the respective results are provided.