Automation of machines is becoming increasingly widespread and advanced, of which an example is the use robots for Prime Vision, which sorts parcels for postal services. The coordination of scheduling a fleet of robots picking up and dropping off many parcels while avoiding collisions, within a limited space, following predefined routes in a floorplan, is a complex problem.

This logistical challenge can be effectively modelled using max-plus linear algebra to allow an optimization for the route scheduling as was previously done by L. Smeets. The goal of this research is to improve the existing scheduling model and use this to develop a reinforcement learning-based algorithm that determines the optimal floorplan for the parcel delivery robots. Two methods are applied to improve the existing scheduling model. Firstly, nodes where no decisions are made are identified and removed. Secondly, certain constraints are also removed to simplify the model.

The results of the scheduler are used to determine a key performance indicator to allow a reinforcement learning based algorithm to identify the optimal floorplan for the robots. The reinforcement learning algorithm employed a deep Q-learning approach, with the neural network trained using various action space approaches, tuned rewards and hyper-parameters. The greedy-epsilon method was applied to address the exploration vs. exploitation problem. While the scheduler improvements significantly enhanced its computational costs, the neural network did not converge, and the potential causes are thoroughly discussed.

Sorting systems form an example of event driven systems. These types of systems are referred to as discrete event systems (DES), and they consist of jobs that need to be performed at available resources. In an autonomous sorting system, jobs consist of robots receiving and delivering parcels at the correct locations. With scheduling, optimal allocation of the jobs to those resources over time is computed, where the decisions that need to be made are routing, ordering and synchronization. The behaviour of DES is often described by non-linear models, but max-plus linear (MPL) systems are a class of DES that can be described by a model that is linear in the max-plus algebra. This algebra uses two operators maximization and addition. Allowing different routes and switching between orders of jobs extends an MPL system to a switching max-plus linear (SMPL) system. Robots in a sorting system often have many routes to choose from, and need to make order choices with respect to other robots in the system.

In this thesis, a general SMPL model is made for the autonomous sorting system at software company Prime Vision, which can be applied to any sorting area design. The solution to the scheduling problem for the model results in a time schedule for the active robots at the correct locations in the sorting area, as well as the optimal decisions on routing, ordering and synchronization. The optimization problem is solved with a model predictive scheduling (MPS) approach and recast as a mixed integer linear programming (MILP) problem. The model is created in Python and the optimization problem is solved with Gurobi. The resulting schedule is visualized with a simulation, in which the decisions of the robots are clearly shown. An idea for implementation of the optimization into the sorting system is given as well.