In recent years, professional first responders have started to use novel technologies at the scene of disasters in order to save more lives. Increasingly, they use robots to search disaster sites. One of the most widely and successfully used robot platforms in the disaster response domain are unmanned aerial vehicles (UAVs). UAVs allow remote inspection and mapping. They are able to provide high resolution imagery and often need minimal infrastructure to fly. This allows settings where multiple UAVs are airborne accelerating the information gathering from the disaster site. However, current deployments use labour intensive, individually teleoperated UAVs. Given this, there is a drive toward using multiple robots operating with a certain level of autonomy, in order to decrease the operators' workload. One approach for utilising multiple robots in this way is semi-autonomous operation supervised by a small number of professionals; only requiring human experts for crucial decisions. Current commercial UAV platforms also allow the deployment of a diverse group of robots, allowing them to combine their individual capabilities to be more ecient. For example, xed-wing UAVs are capable of flying faster and carry larger payload, but when they do so, they should be deployed with higher safety measures (safety pilots are required for non-lightweight aircraft). On the other hand, small rotary-wing UAVs are more agile and can approach and provide imagery about objects on the ground. To this end, this thesis develops a number of new approaches for the collaboration of a heterogeneous group of robots in disaster response. More specifically, the problem of collaborative planning with robots operating in an uncertain workflow based setting is investigated by solving the search and rescue (SAR) collaboration problem. Of course, the problem complexity increases when collaborating with dierent robots. It is not different in this setting, the actions of dierent types of robots need to be planned with dependencies between their actions under uncertainty. To date, research on collaboration between multiple robots has typically focused on known settings, where the possible robot actions are dened as a set of tasks. However, in most real world settings, there is a signicant amount of uncertainty present. For ii example, information about a disaster site develops gradually during disaster relief, thus initially there is often very little certainty about the locations of people requiring assistance (e.g. damaged buildings, trapped victims, or supply shortages). Existing solutions that tackle collaboration in the face of uncertain information are typically limited to simple exploration or target search problems. Moreover, the use of generic temporal planners rapidly becomes intractable for such problems unless applied in a domain-specific manner. Finally, domain specific approaches rarely involve complex action relations, such as task dependencies where the actions of some robots are built on the actions of others. When they do so, decomposition techniques are applied to decrease the problem complexity, or simple heuristics are applied to enhance similar collaboration. Such approaches often lead to low quality solutions, because vital action dependencies across different roles are not taken into account during the optimisation. Against this background, we oer novel online planning approaches for heterogeneous multi-robot collaboration under uncertainty. First, we provide a negotiation-based bidirectional collaborative planning approach that exploits the potential in determinisation via hindsight optimisation (HOP) combined with long-term planning. Second, we extend this approach to create an anytime Monte Carlo tree search planner that also utilises HOP combined with long-term planning. In online planning settings, such as SAR, anytime planners are benecial to ensure the ability of providing a feasible plan within the given computational budget. Third, we construct a scenario close to physical deployment that allows us to show how our long-term collaborative planning outperforms the current state of the art path-planning approaches by 25 %. We conclude that long-term collaborative planning under uncertainty provides an improvement when planning in SAR settings. When combined, the contributions presented in this thesis represent an advancement in the state of the art in the eld of online planning under uncertainty. The approaches and methods presented can be applied in collaborative settings when uncertainty plays an important role for defining dependencies between partial planning problems.