Coordinating multi-robot systems (MRS) have a wide range of application domains including collaborative autonomous manufacturing, automated transport of goods in warehouses and factory floors, environmental monitoring, search and rescue, surveillance, and sensing data collection. Two fundamental problems arise naturally in the autonomous operation of the multi-robot system: (a) multi-robot task allocation; (b) multi-robot path planning. Generally speaking, multi-robot task allocation solves the following problem: given a set of robots and tasks with each robot obtaining a certain payoff for each task, compute a subset of tasks for each robot such that a team performance criterion is optimized subject to a set of constraints on the tasks and/or the robots. Multi-robot path planning solves the following problem: given the initial positions of a set of robots and target positions of the spatially distributed tasks, compute a collision-free path for each robot from its initial position to its target position. Most current works on multi-robot task allocation consider as deterministic parameters like robot-task payoffs, resource consumption of robots performing tasks. However, these parameters may not be known exactly in practice, especially in the open environment in which there are other (uncontrolled) moving entities like humans or human-operated vehicles that occupy the space. One goal of this thesis is to formulate multi-robot task allocation problems with uncertain parameters and develop solution algorithms for them. Further, in the extant literature, task allocation and path planning problems are commonly considered separately. In particular, it is assumed in task allocation that there are planned paths for all robot-task assignments and thus the payoff or the resource consumption to perform a task is available. In path planning, it is assumed that the tasks are assigned to robots and target positions are thus specified. When both problems have to be solved, the decoupling approach (solving two problems separately) is usually used. Although conceptually convenient, the decoupling approach may lead to sub-optimal solutions. Therefore another goal of this thesis is to simultaneously compute the allocation of tasks to robots as well as plan the path from the initial position of robots to the destinations.