An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem We consider multiagent transport task problems where, e.g. in a factory setting, items have to be delivered from a given start to a goal pose while the delivering robots need to avoid collisions with each other on the floor.We introduce a Task ConflictBased Search (TCBS) Algorithm to solve the combined delivery task allocation and multiagent path planning problem optimally. The problem is known to be NPhard and the optimal solver cannot scale. However, we introduce it as a baseline to evaluate the suboptimality of other approaches. We show experimental results that compare our solver with different suboptimal ones in terms of regret.

Scheduling of Mobile Workstations for Overlapping Production Time and Delivery Time Many existing mobile service robots, including the robots in RobocupHome, perform their designated tasks only when the robots are stationary. The efficiency of these robots can be improved if they can perform some tasks while moving. In this paper, we propose the concept of mobile workstations, which combine mobile platforms with production machinery to increase efficiency by overlapping production time and delivery time. We present a model of mobile workstations and their jobs and describe the task planning algorithm for a team of mobile workstations. The temporal planning problem for mobile workstations combines both features of job shop scheduling problems (JSP) and traveling salesman problem (TSP), but there is little work in the literature that tackles both JSP and TSP simultaneously. Our first algorithm is a complete search algorithm which returns an optimal temporal plan with minimum makespan, and our second algorithm conducts a local search in the space of task graphs so as to quickly return suboptimal temporal plans. According to our experiments, when the number of jobs is small, our second algorithm can generate nearoptimal temporal plans, and when the number of jobs is large, our algorithm can generate much shorter plans than SGPlan 5 and a version of job shop scheduling algorithms.