This paper describes the design, fabrication and locomotion of a starfish robot whose locomotion principle is derived from a starfish. The starfish robot has a number of tentacles or arms extending from its central body in the form of a disk, like the topology of a real starfish. The arm, which is a soft and composite structure (which we call the smart modular structure (SMS)) generating a planar reciprocal motion with a high speed of response upon the actuation provided by the shape memory alloy (SMA) wires, is fabricated from soft and smart materials. Based on the variation in the resistance of the SMA wires during their heating, an adaptive regulation (AR) heating strategy is proposed to (i) avoid overheating of the SMA wires, (ii) provide bending range control and (iii) achieve a high speed of response favorable to successfully propelling the starfish robot. Using a finite - segment method, a thermal dynamic model of the SMS is established to describe its thermal behavior under the AR and a constant heating strategy. A starfish robot with five SMS tentacles was tested with different control parameters to optimize its locomotion speed. As demonstrated in the accompanying video file, the robot successfully propelled in semi-submerged and underwater environments show its locomotion ability in the multi-media, like a real starfish. The propulsion speed of the starfish robot is at least an order of magnitude higher than that of those reported in the literature-thanks to the SMS controlled with the AR strategy.