Methods and apparatus are provided for allocating tasks to be performed by one or more autonomous vehicles to achieve a mission objective. Generally, a task allocation system identifies a final task associated with a given mission objective, identifies predecessor tasks necessary to complete the final task, generates one or more candidate tasks sequences to accomplish the mission objective, generates a task allocation tree based on the candidate task sequences, and searches the task allocation tree to find a task allocation plan that meets a predetermined selection criteria (e.g., lowest cost). Based on the task allocation plan, the task allocation system determines a task execution plan and generates control data for controlling one or more autonomous vehicles to complete the task execution plan.