XST iRobot – OMiLAB Robotic Picking and Path Finding Experiment

Source code:

Use Case

The aim of this project is to provide a universal model based solution for automatic route planning and picking job execution in warehouse environments. Our research has shown that existing warehouse operations are typically performed by human beings. Related tasks are typically not mentally stimulating, repetitive, and exhaustive. Thus they can potentially negatively affect the wellness of the assigned workers. Hence, the proposed approach should ease the handling and picking of goods from warehouse storage areas based on metamodels, models, genetic algorithms, and robotics.

The solution provided in this project tackles three challenges:

  1. The design and definition of the warehouse area based on visual modeling components. This enables workers to define and describe the warehouse (e.g., the floorplan but also the positioning of goods or points were picked goods can be delivered to). For this the ADOxx modeling environment is utilized along with a hand crafted meta model which is optimized for the given task at hand.
  2. The definition of additional relevant details. For example, some goods have unique transportation requirements (e.g., cooling) which can only be fulfilled by a selection of all available transportation robots (e.g., that contain a cooling element). To enable the quick and seamless description of these aspects (but alsoin a machine-readable way) ontologies can be applied. Hence, this challenge is tackled with the creation of a specialized ontology which enables to describe products, robots, and their requirements and features\properties.
  3. Finally, whenever a new picking job becomes available a suitable robot needs to be selected and sent on its journey through the warehouse to collect the required goods. This requires a) to receive orders, b) select appropriate robots, and c) identify optimal paths for the robots to travel upon. While aspect a) is tackled based on a hand-crafted order description format (specified by utilizing XML Schema); aspect b) is solved based on the ontology from 2). Finally, aspect c) is tackled by a genetic algorithm based wayfinding approach.

The solution is implemented based on three components. The metamodel and example warehouse floor plan models were created and can be utilized based on ADOxx (https://www.adoxx.org/). The ontology which describes the properties of all mobile components (robots and goods) were created but also can be viewed and edited with Protege (https://protege.stanford.edu/). Finally, the wayfinding was implemented based on a hand-crafted prototypical application which holds a custom implementation of the genetic algorithm concept which was optimized for the given wayfinding task (i.e., finding shortest routes in the warehouse floorplans for the robots to travel opon). All components (source code, implemenation, executables, libraries, and test data) can be found in the following GitLab project: https://gitlab.dke.univie.ac.at/a1026133/XSTiRobot

The desktop application is implemented in Java Swing and looks like this (you can also see the model created with ADOxx in comparison to the imported model):

A video recording (demo) of the application and it behavior is given under “Results”.

Experiment

This experiment was split into three different Use Cases which will be described in the following along with their necessary components.

  • Use Case 1: Creation of a Metamodel using ADOxx to get a machine-readable illustration of the warehouse floorplan as well as the model import via XML and visualization of such an imported model in the simulation environment.
    • Created Components: Metamodel, models based on the metamodel and a Simulation Environment.
  • Use Case 2: Implementation of a genetic algorithm, to find for a randomly chosen robot and product an optimal (shortest) path for the pick job execution. Hereby, the applicability of the implemented genetic wayfinding approch is shown.
    • Created Components: Extension of the Simulation Environment through the implementation of the genetic wayfinding algorithm.
  • Use Case 3: Extension of the implementation by adding components which enable to integreate a) ontologies to find an optimal robot and product assignment and b) orders which require to pick goods from the warehouse.
    • Created Components: Ontology, orders and an extension of the Simulation Environment to extract and combine information given in the ontology and the order. Futher, the picking job is planned for the given order and the related movement of the robots can be visualized.

Description of the created main components:

The following text describes the four main components of this project. This is the ontology which described the properties of goods and robots, the metamodel which enables to define warehouse floorplan models, the orders which need to be defined based on a given XML Schema, and the main application which enables to display floorplans but also to calculate and simulate the behavior of robots. Further the DevOps section gives additonal details on the technology used in this experiment.

Metamodel and Model

The metamodel enables to describe the floorplan of a warehouse. Hence, it enables to describe the position of pallets (holding goods), delivery points (were the robots can return after they have picked a good from a pallet), robots (amount and type), and hallways (also referred to as aisles) which enable to describe the ways robots can utilize to move between different places in the warehouse. Further hallways enable to define a specific place a pallet or delivery point can be found (i.e., accessed by a robot). Given this metamodel the visualization of the warehouse floorplan can be created as model. Note that during the creation of the model, it is important to utilize the given connectors to combine all the different parts of the floorplan and for good visualization results in the simulator you need to give all parts an order of their visibility (e.g. robots need to be on top of all other parts, otherwise the will hide behind pallets or hallways during the picking job execution visualization in the simulator). Further, this enables the path finding algorithm to determine how all places are connected with each other and how to travel between them. Not connected pallets or hallways are left out, so the will not be visited and goods on such pallets will never be found, which shows why correctly utilizing the giving connectors (when creating the floorplan model) is important. Finally, it also enables to determine from which part in the warehouse, e.g., a specific pallet can be reached by a robot to pick up a good from it. The metamodel must be imported into ADOxx to create the respective floorplan models. To import created models into the simulator it needs to be exported as XML. The metamodel with a created example model and an excerpt oft the resulting XML representation is given below.

Ontology

The ontology contains two main components. These are goods and their properties (e.g., if they require cooling) but also information about the robots (e.g., if they contain a cooling element). The connection between the model and the ontology and its information is created based on unique IDs assigned to each robot and good stored on a pallet. It is important that the IDs in the ontology and the models are consistent but also that the assigned attributes for the visualization are consistent (cooling product should be stored on a pallet marked as a cooling pallet). However, the latter is mere relevant for the visualization but does not interfere with the correctness of the picking job plannig and execution. The created ontology needs to be stored as RDF/XML and can then be imported into the simulator. A graphical representation of the used ontology is given in the following:

Order

Each order is defined in XML and has to comply with the following XML Schema. An order data structure can contain multiple articles but at the only moment the first article is picked during the simulation.

To summarize the experiment, I have created a overview graphic which depicts all utilized components used:

DevOps

In this section, the main application which enables to display floorplans but also to calculate and simulate the behavior of robots is described as well as the technologies used and how to start the experiment.

Execution of the Experiment

  • Based on the executable JAR file:The project is self-contained. Hence, all libraries, data sources, images, etc. are contained in the project data structure. So, starting the executable Jar file with java -jaris sufficient (the executable jar can be found in the related GitLab project).
  • In the development environment: In the project caled “Visualization” the package “main” holds a class named “mainView.java”. This class represents the main entry point for the project and starts the application.

Experiment Requirements and external libraries

  • Requirements: The project was fully implemented in the Java programming language. Hereby, features from Java 1.8 were utilized, hence at minimum Java 1.8 must be installed when executing the project but also when working on future project extensions.
  • External Libraries: All libraries are contained in the project named Libraries. From all libraries stored there only the owlapi-distribution-5.1.3.jar library is used directly by the application. All other libraries are required by this library and used indirectly by it.
  • Remaining Technology:
    • Entwicklungsumgebung: Eclipse Oxygen
    • Programmiersprache: Java 1.8
    • XML Library: SAX Parser (Java Komponente)
    • Modellierungstool (Metamodell, Modell): ADOxx
    • Ontologie: Protégé
    • Ontologie Parser: OWL API
    • Datanaustauschformate: XML, RDF/XML
    • Visualisierung: Java Swing

Project Structure

The project is fine granularity structured into multiple (sub)projects. Each one represents one specific feature block utilized by the project. The following description is based on this project structure.

  • Helpers: Holds helper and util classes which simplify the handling of collections (e.g., if a list is null or empty), random data (e.g., random selection if items from streams), and data structures. For example, by providing objects to represent tuples.
  • Images: Holds and allows the access on all images utilized by the application. For example, each robot, aisle, etc. is visualized based on a binary image. These images were created based on the model class instance visualization given in ADOxx. The ImageHelper class enables to access the correct image for a specific class instance for the built-in model visualization.
  • PathFinding: Calculates, based on a genetic algorithm, an “optimal” for a graph network data structure. For this it is assumed that the graph holds only nodes which are directly connected to other adjacent nodes. Hereby, the floorplan of the warehouse model is represented (connections between the individual model instances are taken into consideration, e.g., how hallways and pallets are connected/related to each other). The main idea of the algorithm is that an individual holds a list of genes which represent multiple individual steps/directions, e.g., to move left, right, down, up. Hereby, one can move between one network node and another connected one. Based on Multi Point Crossover, Roulette Wheel Selection, and Mutation various possible step orders are analyzed till one with a minimum length is found (i.e., which enables to move from one node to another with the shortest possible traveled distance). The implemented algorithm executes a fixed number of generations and returns the shortest path found (i.e., the algorithm strives to minimize the problem). For fitness calculation two approaches are applied: If the targeted node is reached (foune) based on a given path the path length is used. Otherwise, the fitness is the number of unique nodes covered by the path plus the path length. Hereby, paths that cover more space are preferred as this increases the likelihood that the targeted node is found.
  • ReadModelData: Reads the model data exported from ADOxx. It is expected that the model is exported into an XML file following the standard ADOxx XML format. This enables to get access on the floor plan modeled based on the metamodel defined in ADOxx.
  • ReadOntologyData: Read the ontology data which was defined in Protégé and exported as RDF/XML. The ontology holds details and properties of each good stored in the warehouse but also about each robot. Mainly this information is utilized to select which robot should transport a specific good defined in an order. For this this project contains the necessary code to determine for a given robot which goods it can transport.
  • ReadOrderData: Reads an order. For this the order data must be defined in XML and has to follow the format given in the respective schema.
  • Visualization: The visualization project combines all other projects to visualize a warehouse floor plan model and to simulate the execution (picking actions) for a given order. For this it contains a number of menu entries, which enable to read in all the data individually and visualize how the robots follow the calculated paths. The user interface utilized Java Swing. To ease the handling and understanding of the graphical interface the most important features are organized based on the described three main use cases.

Evaluation

The fulfillment of each Use Case was evaluated based on a prototypical implementation (artefact). This approach enabled me a) to verify it the planned approaches and concepts meet the given requirements and b) if the quality of the achieved results could be assumed as being sufficient. Both aspects were found to be sufficiently implemented and the given requirements were fulfilled (e.g., the genetic wayfinding implementation almost always found the shortest path possible). 

Future Work

  • Extend the genetic algorithm to pick more than one product
  • Combine simulation and real world robots
  • Integrate services, so that the order can come from a REST interface
  • Integrate a service, so that the model can directly be imported from ADOxx

Results

Finally, to illustrate the results of this project a video was created. The video shows three main use cases tackled with this project. These are:

  • Use Case 1: the loading and visualization of the warehouse model (floorplan)
  • Use Case 2: the calculation and simulation of random picking jobs (e.g. randomly chosen picking robots and goods)
  • Use Case 3: the execution of externally provided picking jobs. For this the ontology (descripting good and robot properties) and the picking jobs are analyzed. Subsequently, an optimal robot is chosen for the job and send on its way to execute the picking order. Hereby, the path followed by the robot is calculated by the described genetic wayfinding approach. This should ensure that the utilized path is as short as possible (or close at this target).