SokoRam

Project Conception

In 2017, the Bureau of Labor Statistics reported an average of 5.1 injury cases per 100 full-time workers in the warehouse and storage industry. With roughly a million non-supervisory workers in the sub-sector, it begs the question: what steps can be taken to prevent these injuries? An answer many have arrived at is automation. In order to explore the benefits, limitations, and optimizations that can be involved, our project models automatized warehouse management as a game of Sokoban.

What is Sokoban?

Sokoban is a puzzle game where the player is required to push crates to appropriate storage locations while their movement is limited by the walls and the crates themselves. The game was invented in 1981 by Hiroyuki Imabayashi and holds numerous parallels to real life warehouse management. There has been quite some research on creating AI to solve the game of Sokoban, but while methods such as single-agent search algorithms have found some success, more convoluted levels of Sokoban are out of reach for computers (the problem is NP-hard). Luckily, real-life organization scenarios aren't nearly as complicated as the hardest levels in Sokoban.

Goals

Our Sokoban setup consists of two main parts: a small-scale board and a full-scale field. The field represents the actual warehouse with our robot and crates to move while the board mimics the setup on the field, excluding the robot. Any movement to the "crates" on the board will immediately signal to the robot that it must move the crate on the field to mimic the board. In a real life application, the small-scale board could be a digital or physical representation of the warehouse and upon the need to reorganize or retrieve items, the necessary command would be not only intuitive but efficient.

With the context of this project in mind, we had a few end goals:

Correctly relocate the crate to the corresponding block coordinates using the Turtlebot
Turtlebot proves successful in its mission regardless of initial configuration (provided bot is visible)
Navigation updated in real-time, even under adversarial conditionals
Keep the entire process accurate and timely

While journeying our way through this project, there were a few key concepts we wanted to explore and experiment with. The first being different ways of aligning the coordinate system of the small-scale board with the full-scale board which led us through multiple methods of object detection. The second was optimal path planning: finding efficient paths not just in terms of shortest distance, but with clear push paths that would give consistent pushes, saving time that would have been needed for small corrections and adjustments. Finally, and most challenging, we also delved into adversarial conditions for the robot, proposing possible unexpected interference with the robot and programming the necessary adjustments to assure successful and reliable movements.

One of the hardest struggles was the hardware limitations, which severely hindered our ability to precisely locate all relevant objects on both the board and field. Along the way we also found many trade-offs we had to balance. Primarily, we found ourselves concerned with accuracy vs. speed and efficiency vs. complexity which really shaped the way we designed this project.

The presence of adversarial conditions as well as the misalignment between the square surface of the crate and the cylindrical surface of the Turtlebot present new, challenging tasks with many real-world implications, creating an interesting, fresh take on a traditional problem.

Report abuse