Scheduling autonomous robots for an intralogistic application: a comparison of lookahead-based ADP strategies

The increasing role of e-commerce has spurred a significant amount of research on optimization in warehousing management, including routing and scheduling issues. When material handling is rigidly automated, a deterministic scheduling problem arises, for which solution strategies have been proposed in the literature. A recent trend is the introduction of autonomous robots, which may interact with human operators and offer additional flexibility in item manipulation. The resulting problem is affected by uncertainty, due to the interaction between robots and human workers and the possible failure in items manipulation. In the paper, we propose an adaptation of approximate dynamic programming strategies with limited lookahead, namely, rollout strategies and Monte Carlo tree search. The idea can be interpreted as an intermediate approach between the solution of a deterministic problem, disregarding uncertainty and using a long lookahead, or the application of pure state-based dispatching rules with no lookahead. The proposed approaches are compared against exact dynamic programming on small-size instances, and then evaluated on larger instances, proving their viability.