After a terrible disaster such as an earthquake or a nuclear accident, finding victims and isolating them from hazards are usually the first priorities for rescuers. As the security of rescuers and the stabilization of the environment are critical components of the first rescue phase, we assume that robots could be used to secure the environment by performing construction tasks, to stabilize large structures, and/or protect the victims. In this paper we suggest an approach consisting of using mobile robots to construct protective walls on a site affected by a nuclear disaster. Protective walls can help to block radiation from toxic sources and protect both victims and rescuers. On the other hand, the robot’s vulnerability to radiation restricts its freedom of movements into unsafe regions. Therefore, building protective walls needs a plan (construction plan) that involves three competing objectives: victim safety, rescuer safety, and robot safety. Weighting these factors is a societal choice, is not trivial, and impacts the whole system. In this paper, we provide and optimize the construction plan using a genetic algorithm based on three objectives. We analyze the construction plan performance with respect to execution time. We also analyze the trade-offs involved between these competing objectives in different environments with ranging physical complexity (e.g., a number of victims or sources).