Blog
3. Hackathon: Ehrenlunch - du bist was du isst
Von Oliver Schick am 21. März 2022
Gegen 12 Uhr kommt bei uns im Team regelmäßig eine kleine “Mittagsunruhe” hinein, weil wir uns abstimmen, wer was und wo zu Essen bestellen möchte. Diese Abstimmung geht mal mehr und mal weniger schnell. Nachdem das Essen bestellt und das Geld meist von einer Person ausgelegt wurde, ist es dann immer aufwändig, dass die einzelnen Beträge wieder an diese Person zurückkommen.
Um den Ablauf der Bestellung und der gegenseitigen Bezahlung zu optimieren, haben wir uns entschieden, dieses Problem zum Thema unseres 3. Hackathon zu machen. Das Ziel war es, innerhalb eines Tages eine App dafür zu entwickeln, da uns schon bestehende Lösungen nicht gefallen haben.
Ablauf:
Um 9 Uhr führten wir zu Beginn einen kurzen User-Story-Mapping-Workshop durch, bei dem wir in einem Brainstorming mögliche Features der App erarbeiteten und diese dann anschließend priorisierten. Diese Priorisierung war wichtig, damit wir uns auf die sinnvollsten Features fokussieren können und so am Ende des Tages auch ein funktionierendes MVP (Minimum Viable Product) haben. Folgende Ideen für Features haben wir gesammelt:
- Rechnung durch Abfotografieren oder manueller Eingabe erfassen (Bilderkennung)
- optimale Aufteilung der Salden, damit am Ende eines Zeitraums untereinander so wenig Transaktionen wie möglich getätigt werden müssen, um die Schulden zu bezahlen (Optimierungsproblem)
- Abhängig von anwesenden Personen und Wochentag: Vorschlag für die ganze Gruppe in welches Restaurant man geht (Recommender-System)
- Für jeden User individuell: Welches Gericht am besten zu ihm passt (Recommender-System)
In der Priorisierung kam heraus, dass wir uns am heutigen Tag auf die Erfassung (Bilderkennung), die optimale Aufteilung der Rechnung (Optimierungsproblem) und das User-Interface fokussieren werden.
Grund dafür war, dass wir für die Recommender-Systeme eine breite Datenbasis zu den Restaurants und den Vorlieben der User brauchen, die wir noch nicht haben. Unsere Idee war deshalb, dass wir erstmal eine App entwickeln, die uns schnell und effektiv bei der Bezahlung hilft. Bei der anschließenden Nutzung der App können dann verschiedene Metadaten zu den Restaurants und Vorlieben der User gesammelt werden, um dann diese Daten im nächsten Hackathon für das Recommender-System zu nutzen.
Wir teilten uns in die drei Teams Infrastruktur & Backend, UX & Frontend und Features (Bilderkennung und Optimierungsproblem) auf, um in kleinen Teams an den Einzelteilen der Idee zu arbeiten. Nach einem kurzen Sprint in den kleinen Teams, trafen wir uns in der großen Runde, um die Integration zu planen, indem wir die API-Endpunkte besprachen. Nach der Mittagspause, in der wir durch Bestellungen Testrechnungen für die App generierten, arbeitete jedes Team intensiv knapp 3 Stunden an seinen Aufgaben. Um 16 Uhr besprachen wir den Zwischenstand und was noch zu tun ist, damit die App stabil laufen kann.
Team Objekterkennung:
Da es sich bei Rechnungsbelegen um ein standardisiertes Objekt handelt, war es uns in diesem Fall möglich, auf eine Standardlösung zurückzugreifen. Wir haben uns für den textract-Service von AWS entschieden. Dieser Service ermöglichte es uns, fotografierte Rechnungsbelege digital zu erfassen. Dabei werden die Fotos zunächst an AWS gesendet und mithilfe eines trainierten KI-Modells verarbeitet. Als Rückgabe erhält man Schlüsselinformationen wie Name des Restaurants, Liste der Mahlzeiten mit Anzahl, Preis, etc. in json-Format. Diese Schlüsselinformationen konnten wir im Anschluss weiterverarbeiten und in unserer Ehrenlunch App darstellen.
Team Optimierung:
Als zentrale Funktion in der App, soll das Bezahlen des Mittagessens erleichtert werden. Beim Abholen spart man Zeit (und Nerven), wenn einer die komplette Rechnung begleicht. Dies führt allerdings dazu, dass sich verschiedene offene Zahlungsbeträge zwischen den Nutzen ergeben.
Wir haben uns dazu entschieden, die Zahlungen der User in Salden zusammenzufassen. Hierbei werden alle noch offenen Positionen erfasst und dem passenden User als Guthaben bzw. Schulden zugeordnet.
In einem zweiten Schritt stellt sich die Frage, wie die unterschiedlichen Salden mit möglichst wenig Zahlungstransaktionen zwischen den Usern ausgeglichen werden können. Hierfür haben wir uns entschieden, ein ILP (Ganzzahlig Lineares Optimierungsproblem) zu verwenden. In diesem Optimierungsproblem werden die Anzahl der Zahlungsströme minimiert, unter der Nebenbedingung, dass unter Anwendung der vorgeschlagenen Zahlungen, die Salden ausgeglichen sind. Sprich: Alle Schulden werden mit möglichst wenig Aufwand beglichen.
Unsere Zielfunktion:
Die Lösung unseres Optimierungsproblems liefert uns optimale Zahlungsvorschläge, die in der App dem User dargestellt werden und sich bei jeder neuen Aktivität, auf Basis der neuen Salden, aktualisieren. Wichtig war für uns, dass die berechneten Zahlungen nur als Vorschlag dienen. Die User können beliebige Zahlungen untereinander leisten und diese in der App erfassen. Alle geleisteten Zahlungen werden vor der nächsten Optimierung erfasst und in die Berechnung miteinbezogen.
Fazit:
Nach einem kurzen Endspurt am späten Nachmittag sahen wir uns gemeinsam das Endergebnis an. Neben einer App mit individuellem Login, bei der man automatisch (über ein Foto der Rechnung) und manuell die Rechnungen erfassen kann, haben wir außerdem eine Datenbank konzipiert, in der die einzelnen Salden der Rechnungen erfasst werden und die mit einer minimalen Anzahl an Transaktionen bezahlt werden können. Wir waren alle sehr zufrieden und stolz auf das Endergebnis und möchten in den kommenden Wochen noch etwas an der Anwendung arbeiten, um kleinere Bugs zu beheben und die App dann jeden Tag für die Planung und Abwicklung des Mittagessens zu verwenden.
Sie möchten mehr über die individuelle Entwicklung von KI-Projekten erfahren und interessieren sich dafür wie auch Ihr Unternehmen von Künstlicher Intelligenz profitieren kann?
Kontaktieren Sie uns gerne für eine unverbindliche Beratung.