The current autonomous mobility systems for planetary exploration are wheeled rovers, limited to flat, gently-sloping terrains and agglomerate regolith. These vehicles cannot tolerate instability and operate within a low risk envelope (i.e., low-incline driving to avoid toppling). Here, we present ‘Mars Dogs’ (MD), four-legged robotic dogs, the next evolution of extreme planetary exploration. MD is a novel system concept for acquiring science return from hard-to-access planetary surface & subsurface regions. MDs can negotiate extreme terrains using unique failure-recovery behaviors, providing a major breakthrough in planetary traversability. MDs are lightweight, compact, and fast-moving compared to Perseverance: 2.6% volume, 4.6% mass, and 38 times faster. A pack of MDs consists of three individual robotic units: one (Alpha-MD) equipped with a deep cave exploration payload including an arm; and two (Tether-MD) equipped with a tethering system. One of the units carries a MMRTG power supply. Each MD is equipped with sensors and deployable communication nodes to facilitate live, subterranean-to-surface data transmission. Mars Dogs operate in synergy, exhibiting collaborative mobility behaviours to accomplish diverse missions that cannot be fulfilled by a single robot. An array of lava tubes on the southeastern flank of Pavonis Mons in the Tharsis Region of Mars offers an ideal location to release a pack of Mars Dogs. This region is of interest to scientists as it offers access to the Mars subsurface, where evidence of past or extant life may persist, and a potential shelter to future human inhabitants. The MD concept has evolved from our experience using the stable and nimble Boston Dynamics “Spot” quadruped. We endowed Spot with a high-level autonomy/AI framework referred to as “NeBula”, developed by our JPL/Caltech Team CoSTAR. Our “Autonomous Spot” platform has advanced the current state-of-the-art in legged exploration and traversal of extreme and subsurface environments, propelling us to a 1st-place finish in the 2020 DARPA Subterranean Challenge with a system similar to that which we envision for Mars Dogs. Through partnership with the NASA BRAILLE Team, we will apply this technology to the exploration of lava tubes in N. California, an analog environment for future missions to volcanic caves on Mars.