Safety Assessment for Motion Planning in Uncertain and Dynamic Environments
Daniel Althoff · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2014
The progress of robotic systems in the past decades provides robots with capabilities to operate in human populated environments.One of the major challenges on the way to obtain the objective of the robot co-worker is to ensure a safe and reliable operation of robots.Consequently, motion safety is becoming increasingly important in robotic research.This thesis investigates novel safety assessment and motion planning methods for robot navigation in dynamic and uncertain environments with contributions to three problems.First, the problem of safety assessment of roadmaps in uncertain environments is addressed and a novel approach is presented which computes the safety by the policy with the smallest expected collision probability.This policy determines the optimal route in the roadmap depending on the available information of the environment and enables the robot to replan its route during execution.Compared to the common approach of determining the optimal route, the novel approach is guaranteed to result in a lower collision probability.Second, novel algorithms for the problem of safety assessment beyond the planning horizon of trajectories are presented.Motion planning approaches for dynamic environments usually generate partial trajectories towards the goal since motion prediction is often not reliable for a long time period.The novel approaches are more efficient than previous methods.Moreover, this problem is also investigated in uncertain environments taking into account the uncertainties in the motion prediction of the surrounding objects of the robot.Next, the problem of reliable and efficient navigation in uncertain populated environments is addressed that is nowadays still an open problem, especially if the density of moving objects is high.Due to the high density and the uncertain motion prediction of objects the robot may fail to find any admissible trajectory.This problem is addressed by presenting novel safety assessment concepts that consider the avoidance behavior of reactive objects such as humans.It allows a more reliable and less conservative assessment, especially in dynamic environments with a high density of objects.Finally, the integration of the presented safety assessment approaches into motion planning algorithms is shown.An integration into optimal control approaches is presented that guarantees safety beyond the planning horizon.Based on the idea of the novel roadmap safety assessment approach a generic planner is presented that improves any solution to the motion planning problem by generating additional trajectories resulting in an optimized roadmap.This roadmap is guaranteed to have lower cost than the optimal trajectory.Furthermore, an interactive motion planner is presented considering the avoidance behavior of reactive objects.Thus, the robot and the surrounding objects are reciprocal avoiding each other instead of assuming that only the robot is avoiding the other objects.The effectiveness of all novel methods for safety assessment and motion planning are demonstrated by various simulations from the field of mobile robot navigation and autonomous driving. ZusammenfassungDer Fortschritt der letzten Jahrzehnte im Bereich der Robotik ermöglicht es Robotern in der direkten Umgebung von Menschen zu agieren.Um jedoch das Ziel der Mensch-Roboter-Koexistenz zu erreichen, muss ein für Menschen ungefährlicher Betrieb von Robotern gewährleistet werden.Deshalb spielt die Bewegungssicherheit von Robotern eine immer größere Rolle in der Forschung.Diese Dissertation präsentiert neuartige Methoden zur Sicherheitsbewertung und Bewegungsplanung für Roboter in dynamischen und unsicheren Umgebungen.Zunächst wird die Sicherheit von Roadmaps in unsicheren und dynamischen Umgebungen untersucht und ein neuartiger Ansatz zur Sicherheitsbewertung anhand der Kollisionswahrscheinlichkeit der optimalen Strategie vorgestellt.Diese Strategie wählt die optimale Route der Roadmap abhängig vom aktuellen Zustand der Umgebung aus.Dadurch kann die Route des Roboters neu geplant werden und ermöglicht es dem Roboter auf Veränderungen in seiner Umgebung zu reagieren.Im Vergleich zu vorherigen Ansätzen, welche die Sicherheit anhand der optimalen Route der Roadmap bestimmen, kann so eine weniger konservative Bewertung garantiert werden.Des Weiteren werden neue Ansätze für die Sicherheitsbewertung von unvollständigen Trajektorien jenseits ihres Planungshorizontes präsentiert.Viele Ansätze der Bewegungsplanung für dynamische Umgebungen generieren nur unvollständige Trajektorien zum Ziel, weil die Bewegungsprädiktion anderer Objekte nur für einen kurzen Zeithorizont verfügbar ist.Neue Methoden werden vorgestellt, die eine effizientere Berechnung als vorherige Methoden ermöglichen.Außerdem wurden neue Methoden für unsichere Umgebungen vorgestellt, die Unsicherheiten in der Prädiktion der umliegenden Objekte berücksichtigen.Als Nächstes wird das Problem einer zuverlässigen und effizienten Navigation in Umgebungen mit Menschen behandelt.Dieses Problem ist eine besonders große Herausforderung, wenn es sich um eine erhöhte Anzahl von Menschen handelt.Aufgrund der hohen Dichte und der unsicheren Prädiktion der menschlichen Bewegung ist es manchmal unmöglich für den Roboter eine geeignete Trajektorie zu seinem Ziel zu finden.Um dieses Problem zu lösen werden neue Sicherheitskonzepte vorgestellt, die das Ausweichverhalten von reaktiven Objekten, wie zum Beispiel Menschen, berücksichtigen.Diese Methoden erlauben eine zuverlässigere und weniger konservative Sicherheitsbewertung, besonders in unsicheren Umgebungen mit einer hohen Dichte von Objekten.Abschließend werden basierend auf den neuen Sicherheitskonzepten neue Algorithmen zur Bewegungsplanung vorgestellt.Dazu werden Bewegungsplaner basierend auf dem Konzept der optimalen Steuerung erweitert, um die Sicherheit der resultierenden Trajektorien für einen unendlichen Zeithorizont zu garantieren.Basierend auf dem neuen Ansatz zur Sicherheitsbewertung von Roadmaps wird ein generischer Bewegungsplaner präsentiert, der jede Trajektorie verbessern kann, indem zusätzliche Trajektorien generiert werden, die zu einer optimierten Roadmap führen.Es wurde gezeigt, dass diese Roadmap geringere Kosten besitzt als die optimal Trajektorie.Außerdem wird ein interaktiver Bewegungsplaner vorgestellt, der das Ausweichverhalten von reaktiven Objekten berücksichtigt.Dadurch wird das gegenseitige Ausweichverhalten des Roboters seiner umliegenden Objekte berücksichtigt, anstatt davon auszugehen, dass nur der Roboter den anderen Objekten ausweicht.Die Effektivität aller neu präsentierten Methoden zur Sicherheitsbewertung und Bewegungsplanung wird anhand von zahlreichen Simulationsstudien aus dem Bereich der mobilen Robotik und des autonomen Fahrens veranschaulicht. Safety CriteriaMany common safety assessment approaches or collision avoidance algorithms exists preventing collisions in many cases, but most of them cannot ensure safety in all possible situations.In [31] three criteria are introduced for evaluating common navigation approaches regarding their motion safety in dynamic environments: 1.Consider the robot's dynamics 2. Consider the environment objects' future behavior 3. Reason over an infinite time-horizon.The authors postulate that a safety assessment approach has to take into account all of these criteria.In the following, the criteria are explained in more detail. Consider the robot's dynamicsThe safety of a trajectory can only be evaluated if the robot is able to execute it.Meaning that the trajectory considers the kinematic and dynamic constraints of the robot system.Otherwise, the robot moves along a trajectory that was not evaluated.Consider the environment objects' future behavior A possible collision can only be foreseen, if the future states for all objects in the environment are predicted.Otherwise, the safety assessment approach is only applicable to static environments.Reason over an infinite time-horizon At first, this criteria is confusing, since a robot trajectory is usually only valid for a finite time horizon.However, trajectories which are collisionfree can eventually lead to a collision beyond the valid time horizon of the trajectory.To reason