The development of foundational theory and validated algorithms for human-robot teams operating in complex environments, capable of adapting as knowledge of the environment and tasks evolves over time, is a crucial area of research. As data becomes available, there is a need for evolving planning strategies to effectively utilize the information. In the specific context of search and rescue (SaR) scenarios, the high-level goals are to locate survivors, simulate rescue by having humans meet survivors, and minimize the risk to human team members. Ultimately, we seek to improve human-cooperation under uncertainty, as well as team performance and safety. This thesis explores probabilistic driven multi-agent planning approaches, motivated by the challenges posed by SaR missions.First, we investigate the problem of multi-robot non-adversarial search. Uncertainty is present in the victim’s true location as only probabilistic information is available a priori. In this context, we seek to find the optimal (or near optimal) path that maximizes the likelihood that our search team can intercept the target given a mission deadline. We prove this problem to be NP-hard, and present the first set of Mixed-Integer Linear Programming (MILP) models to encompass multiple searchers, arbitrary capture ranges, and false negatives simultaneously. The adoption of MILP as a planning paradigm allows to leverage the powerful techniques of modern solvers, yielding better computational performance and, as a consequence, longer planning horizons than the previous state-of-the-art. We build upon the proposed models to incorporate the concept of danger,estimated through a human-robot shared scene perception scheme, allowing for environment knowledge to evolve throughout the mission. The trade-off between risk vs reward is explored through conditional planning, based on the distinct agents’ tolerances to danger. We then consider other tasks beyond search in our mission, and ultimately even the planned routes and completion of tasks are modeled in a probabilistic manner. We introduce a novel problem formulation that incorporates probabilistic knowledge of task requirements, dependencies between tasks and their relative locations, heterogeneity of agents’ capabilities and an environment that might change as the agents interact with it. Performance assessment of possible mission plans is thus based on probabilistic predictions and tangible reward concepts for team forming, another important aspect of SaR missions.