This paper presents a novel strategy for the on-line planning of optimal motion-paths for a team of autonomous ground robots engaged in wilderness search and rescue (WiSAR). The proposed strategy, which forms part of an overall multirobot coordination (MRC) methodology, addresses the dynamic nature of WiSAR by: 1) planning initial, time-optimal, and piecewise polynomial paths for all robots; 2) implementing and regularly evaluating the optimality of the paths through a set of checks that gauge feasibility of path-completion within the available time; and 3) replanning paths, on-line, whenever deemed necessary. The fundamental principle of maintaining the optimal deployment of the robots throughout the search guides the MRC methodology. The proposed path-planning strategy is illustrated through a simulated realistic WiSAR example, and compared to an alternative, nonprobabilistic approach.