Abstract
Any algorithm of automatic motion that is intended to be used in city traffic must have its safety proven. That is, it is necessary to prove that all dangerous situations (i.e. potential collisions) will be detected and avoided by the algorithm. Currently, such solution does not exist. Cooperative algorithms are not usable in the real city traffic, since it is not possible to deploy such algorithms on all road users. The most effective and intelligent automatic traffic motion non-cooperative algorithms are based on machine learning and therefore could not have their safety proven, or merely do not address a safety issues. This paper presents an algorithm based on satisficing games theory. Such theory allows for proving that if the safe strategy exists, it would be found by the algorithm. Similar algorithms, which are used in airborne non-cooperative collision detection and avoidance systems constraint behavior of the moving objects based on the laws of physics only. They appear to be unusable in the city traffic due to its high congestion. We have introduced traffic rules as limitations in a model of the road traffic. Such improvement allows for constraining possible trajectories of the road users. In most of the situations this is enough for the algorithm to generate safe collision avoidance strategy. The route is given as a list of consequent road sections. The algorithm uses readings of vehicular on-board sensors to determine current traffic situation and produces a sequence of control actions to move vehicle along the route avoiding potential collisions with obstacles and other road users. To take into the account road users who do not follow the traffic rules, the algorithm is able to detect users who violate the rules. For possible trajectories of such road users, only physical constraints are applied when detecting and avoiding the potential collisions. To validate the algorithm, a simulation model of city traffic has been developed within the REPAST simulation framework. Both algorithms (with and without road regulations) have been implemented and compared using the simulation model. In a course of simulation experiments, it was shown that our algorithm finds efficient solutions in most of the road situations. Safety of the solutions generated by the algorithm is proven based on satisficing game theory apparatus.
KEYWORDS: route planning, city traffic, saticficing games, safety, collision avoidance