The collection and maintenance of relevant data is the cornerstone for automation and streamlining of logistics and transportation; it is also the cornerstone for the digitization at companies, in general. However, many logistics and production companies do not possess all the data they need or the available data is of insufficient quality. As a consequence, much potential for better decision making and introduction of new technologies remains untapped.
Overall, data collection and maintenance usually require significant lump-sum investment and high running cost. Especially if the data should be known exactly, exhaustively and with certainty. An example of such data is the data on the required precedence relations between tasks, such as transport orders. If task i is a predecessor of task j, then task i should be completed before we can start task j. We need all the required precedence relations between tasks. If some precedence relations are unknown, the sequence of tasks generated by a decision support tool or by a control unit of a mobile robot may be infeasible.
A state-of-the-art procedure to collect the data on precedence relations is interviews with experts. Interviews refine the uncertain and incomplete data collected or derived from other sources, such as sensors. To avoid errors, an interview question should be stated to each pair of tasks separately. For example, “Is there a precedence relation between task i and task j” There are three options for an answer:
- “Yes, task i is predecessor of j”.
- “Yes, task j is predecessor of task i”.
- “No, task i and task j are independent from each other”.
Each interview question takes about 3-4 minutes or more. Because (automated) decision making in some logistics and production problems involves about 3.000 tasks, or about 4.5 million (!) task pairs, it is obvious that the collection of complete information is impossible.
Therefore, we study the data collection problem as an optimization problem. For a given number of questions, we determine which questions to ask to optimize the business results.
The tasks and their precedence relations can be modelled as a simple, directed and acyclic precedence graph G=(V,E) with the set of tasks V and the set of arcs E⊆V×V, where each arc corresponds to a precedence relation between the tasks. Because of missing data, the precedence relations E are unknown in practice. However, we can approximate E by a superset of arcs Ē (E⊆Ē) such that every solution that is feasible with this so-called maximum graph Ḡ=(V,Ē) is also feasible for the original planning problem with its unknown graph G. However, solutions outputted based on graph Ḡ may be far away from optimality unless some superfluous precedence relations are removed with help of expert interviews. By removing unnecessary arcs from Ē, we allow for more (and potentially better) solutions and reduce the gap between the true optimal solution based on G and feasible solutions based on Ḡ. As obtaining this information is costly, the goal is to ask the interviewees the questions that help most.
One way is to define a set of questions before the interview which can remove the most arcs in expectation using probabilities pe on whether precedence relation e∈Ē is necessary obtained from other information sources, such as sensors. To improve this, the interviewer can dynamically select the next question after each answer of the expert. Additionally, while deciding on the next question, the outcomes of future answers may be considered (e.g. a question may not remove any edges, but be valuable to determine which questions to ask next, if enough question opportunities remain), which requires the methods of artificial intelligence (AI), such as reinforcement learning also known as approximate dynamic programming (ADP).
|Projektleitung||Prof. Dr. Alena Otto|
|Projekttitel||Learning Precedence Relations with Interviews: Optimization Approaches (Learn2WIn)|
|Projektlaufzeit||01.04.2021 bis 30.06.2021|