Legged robots have captured the imagination of society at large, through entertainment and through the dissemination of research findings. Yet, today's reality of what (bipedal) legged robots can do falls short of society's vision. A big part of the reason is that legged robots are viewed as surrogates for humans, able to go wherever humans can as aids or as assistants where it might also be too dangerous or risky. It is in the expectation of robustness and walking facility that today's research hits its limits, especially when the terrain has granular properties. Impeding progress is the lack of a holistic approach to the cyber-physical modeling and control of legged robots. The vision of this work is to unite experts in granular mechanics, optimal control, and learning theory in order to define a methodology for advancing cyber-physical systems (CPS) involving a tight coupling of the physical with the cyber through dynamic interactions that must be learned online. The proposed work will advance the science of cyber-physical systems by more explicitly tying sensing, perception, and computing to the optimization and control of physical systems whose properties are variable and uncertain. Achieving reliable, adaptive legged locomotion over terrain with arbitrary granular properties would transform several application domain areas of robotics; e.g., disaster response, agricultural and industrial robotics, and planetary robotics. More broadly, the same tools would apply to related CPS with regards to terrain aware exoskeleton and rehabilitation prosthetics for persons with missing, non-functional, or injured legs, as well as to energy networks with time-varying, nonlinear dynamics models. The CPS platform to be studied is that of a bipedal robot locomoting over granular ground material with uncertain physical properties (sand, gravel, dirt, etc.). The proposed work seeks to overcome current impediments to reliable legged locomotion over uncertain terrain type, which fundamentally relies on the controlled interaction of the robot's feet with the physical environment. The research goal is to improve the perception and control of legged locomotion over granular media for the express purpose of achieving robust, adaptive, terrain-aware locomotion. It revolves around the hypothesis that simple models with decent predictive performance and low computational overhead are sufficient for the optimal control formulations as the compute-constrained adaptive subsystem will both learn and classify the peculiarities of the terrain online. The main research objectives will involve: [1] a validated co-simulation platform for legged robot movement over granular media; [2] terrain-dependent, stable gait generation and gait transition strategies via optimal control; [3] online, compute-constrained learning of granular interactions for adaptation and terrain classification; and [4] validated contributions using experimental testbeds involving variable and unknown (to the robot) granular media. Given the high value of the robotic platforms and the research with regards to outreach and participation, they will be used as outreach tools and to create new educational modules for promotion of STEM fields. Further, the multi-disciplinary nature of the work will be highlighted in order to emphasize its importance.