Error Correction of Logistical Data: Using a Distributed Viterbi Approach
Authors
Jensen, Tom Nørgaard ; Philipsen, Mads
Term
10. term
Publication year
2008
Pages
79
Abstract
Afhandlingen undersøger et distributionssystem, hvor mange aktiver cirkulerer mellem flere parter. Hver modtagelse og returnering registreres med RFID-teknologi (radiomærkning), men scanninger kan mangle eller være fejlbehæftede. Da parterne betaler pant for aktiverne, er korrekte registreringer nødvendige for at beregne pant på et retfærdigt grundlag. Derfor ønskes data korrigeret, så aktivernes placering kan udledes, selv når nogle registreringer mangler. Til dette udvikles en estimator, der rekonstruerer aktivernes rækkefølge af lokationer ud fra ufuldstændige RFID-data. Estimatoren bygger på systemets statistiske mønstre og modelleres som en skjult Markov-kæde (en model, der udleder skjulte tilstande fra støjfyldte observationer). Derudover er der opbygget en simulationsmodel af distributionssystemet for at teste, om estimatoren kan finde den korrekte lokationssekvens. Estimatoren er testet i et småskalaforsøg, og resultaterne er ekstrapoleret til fuld skala. I stor skala er beregningstiden høj; algoritmen er kun praktisk anvendelig, når den fordeles på flere processorer. Software til et distribueret setup med elleve lokationer er designet og implementeret i C++. Testresultaterne indikerer, at estimatorens nuværende fejlprocent ikke opfylder det krævede niveau.
This thesis examines a distribution system where many assets circulate among several parties. Each receipt and return is logged using RFID technology, but scans can be missing or wrong. Because parties pay deposits on the assets, accurate records are needed to calculate deposits fairly. We therefore aim to correct the data so asset whereabouts can be inferred even when some registrations are missing. To do this, we develop an estimator that reconstructs each asset’s sequence of locations from imperfect RFID data. The estimator uses the system’s statistical patterns and is modeled as a hidden Markov chain (a model that infers hidden states from noisy observations). We also build a simulation of the distribution system to test whether the estimator can recover the correct location sequence. The estimator is tested in a small-scale setup, and the results are extrapolated to full scale. For large systems, computation time is high; the algorithm is practical only when distributed across multiple processors. We design and implement C++ software for a distributed setup with eleven locations. Test results indicate that, in its current form, the estimator’s error rate does not meet the required target.
[This abstract was generated with the help of AI]