Mobile robots can provide a wide range of value-added services to wireless sensor networks during their operational lifetime. One of them has to do with the replacement of damaged sensors with other functional, passive ones. This scenario has been recently studied as the “Robot-Assisted Sensor Relocation” (RASR) problem. RASR solutions traditionally focus only on one aspect of the problem: minimizing the total distance traveled by the robot.The existing centralized solutions do not take into account the reliability of the passive nodes that are selected as substitutes for the damaged nodes, for instance, their current battery level. With this in mind, we propose a multi-objective optimization (MOO) formulation of the problem, named Reliable Robot-Assisted Sensor Relocation (RRASR), where we consider two more objectives in addition to the trajectory length. These objectives result from the fact that a given passive sensor selected to replace a damaged sensor in the region may not be in perfect condition and that another passive sensor may be a better option. Due to the nature of MOO problems, we must present a diverse set of solutions that exhibit a trade-off among the different decision objectives to a network manager so they may take appropriate action. We evaluate the performance of four state-of-the-art evolutionary MOO algorithms with sensor networks of varying sizes and inflicted damage levels. To the best of our knowledge, this is the first time RASR is approached from an MOO angle.