Autonomous robots are used to inspect, repair and maintain underwater assets. These tasks require energy-efficient robots, including efficient movement to extend available operational time. To examine the suitability of a propulsion system based on undulating fins, we built two robots with one and two fins, respectively, and conducted a parametric study for combinations of frequency, amplitude, wavenumber and fin shapes in free-swimming experiments, measuring steady-state swimming speed, power consumption and cost of transport. The following trends emerged for both robots. Swimming speed was more strongly affected by frequency than amplitude across the examined wavenumbers and fin heights. Power consumption was sensitive to frequency at low wavenumbers, and increasingly sensitive to amplitude at high wavenumbers. This increasing sensitivity of amplitude was more pronounced in tall rather than short fins. Cost of transport showed a complex relation with fin size and kinematics and changed drastically across the mapped parameter space. At equal fin kinematics as the single-finned robot, the double-finned robot swam slightly faster (>10%) with slightly lower power consumption (<20%) and cost of transport (<40%). Overall, the robots perform similarly to finned biological swimmers and other bio-inspired robots, but do not outperform robots with conventional propulsion systems.