SCOPE
A part of the Olin College education is Senior Capstone in Engineering, or SCOPE. SCOPE is a year-long class, in which students work in teams to execute a project of interest for a sponsor company. In my case, I worked with a team of five other students to determine the feasibility of micro fulfillment centers (smaller, more-localized warehouses) for Amazon Robotics.
In our team, we then further split up into software and mechanical subteams. The mechanical team worked on designing the space that people would work in, and I worked with 2 other people on the algorithm subteam, where we designed how a robot system could work in a predefined warehouse.
For this task, we created a model of the warehouse in Python that Amazon designed. We then added a time component and the demand: we generated orders that would come in at random intervals, a system to process those orders and the ability for robots to move in the warehouse as time passed.
With that system in place, we conducted a literature review of task allocation and path planning algorithms. We were looking for an algorithm that could not only optimally allocate a given retrieval task to a robot in the warehouse, but which also adapted well to the intricacies of the system. For instance, there would be cases where -with the addition of more orders for instance- it would be more time-efficient for a robot to give its task to someone else. Likewise, the structure of the warehouse made it so that sometimes multiple robots were needed to retrieve an item.
In our model, we implemented the Hungarian method, auction algorithm, network flows and multiple traveling salesman for task allocation. We simulated scenarios in which all but one variable is held constant, and in the end, we found that the mechanisms that surround the assignment algorithm, rather than the algorithm itself, have more of an impact on the efficiency of the system. Some examples of these mechanisms include how often the algorithm is run and where items are placed in the warehouse. Therefore, our recommendation for Amazon robotics was to switch their paradigm from thinking of algorithm efficiency to creating an efficient overall system.
