Small, light-weight and low-cost missions will become increasingly important to NASA's exploration goals. Ideally teams of small, collapsible robots, weighing only a few kilograms apiece, will be conveniently packed during launch and would reliably separate and unpack at their destination. Such robots will allow rapid, reliable in-situ exploration of hazardous destination such as Titan, where imprecise terrain knowledge and unstable precipitation cycles make single-robot exploration problematic. Unfortunately landing lightweight conventional robots is difficult with current technology. Current robot designs are delicate, requiring a complex combination of devices such as parachutes, retrorockets and impact balloons to minimize impact forces and to place a robot in a proper orientation. Instead, we are developing a radically different robot based on a "tensegrity" built purely upon tensile and compression elements. Such robots can be both a landing and a mobility platform allowing for a dramatically simpler mission profile and reduced costs. These multi-purpose robots can be light-weight, absorb strong impacts, are redundant against single-point failures, can recover from different landing orientations and are easy to collapse and uncollapse. These properties allow for unique mission profiles that can be carried out with low cost and high reliability. We believe tensegrity robot technology can play a critical role in future planetary exploration.