Properties of n-ary hypergroups relevant for modelling trajectories in HD maps

DOI: 10.2478/auom-2022-0024 An. S¸t. Univ. Ovidius Constant¸a Vol. 30(2),2022,161–178 Properties of n-ary hypergroups relevant for modelling trajectories in HD maps ˇ Stˇep´an Kˇrehl´ık, Michal Nov´ak and Melis Bolat Abstract In the paper we show that trajectories used in HD maps of autonomous vehicles can be well modelled by means of n-ary hyperoperations and hypergroups. We investigate some properties of such hypergroups. 1 Introduction Our paper deals with a challenging issue relevant for the self-navigation of autonomous vehicles. It is a continuation of studies in which automata theory, rough sets and various generalizations of algebraic concepts as well as concepts of linear algebra are used to model some aspects of self-navigation such as modelling trajectories or processing information. It is to be noted that autonomous driving requires a set of advanced technologies both in the vehicles themselves and in the infrastructure. Since these technologies must continuously communicate, they need to be linked or even integrated. Obviously, it is a high definition (HD) map, real-time and as precise as possible – and discussed in this paper, that is the key component of autonomous driving. Since our paper relies on the tools of the broad field of algebra, we give a selection of similarly oriented papers. For our own results concerning the topic of self-navigation of autonomous vehicles cf e.g. [12, 13]. Paper [15] gives a real-time analysis of building Normal Distribution Transformation (NDT). There, in one of the steps of the transformation, the point Key Words: autonomous driving, HD maps, hypergroup, n-ary hypergroup, self-navigation. 2010 Mathematics Subject Classification: Primary 20N20, 20N15. Received: 16.07.2021 Accepted: 30.11.2021 161 PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 162 cloud Mis discretized into a grid βwith regularly sized cubic cells βi, i = 1,2, ..., m, according to a predefined cell size. In [26], a novel system architecture including a massive multi-input multi-output (MIMO) or a reconfigurable intelligent surface (RIS) and multiple autonomous vehicles is considered in vehicle location systems. By means of geometrical algebraic notions and properties such as associativity, commutativity and distributivity, the authors transform the global coordinate system into a local one. In [10], the algebraic specification of activities performed during network security risk management is given. This is a useful tool to consider the automation of the process of risk management without considering the implementation issues. The authors of [9] formalise IT security risk management as an algebraic datatype specification to check the consistency of security risk analyses viewed as algebras. Probability of occurrence and severity of consequence are modelled as metrics over attack actions to select optimal countermeasures using multi-objective optimisation. While focusing on security management, their algebraic datatype is an inspiration for a further formalisation of consequences and assets. However, their action abstraction and the use of communicating sequential processes offers a design method for safety controllers as opposed to the more abstract attack model proposed in [10], which focuses on risk assessment. In [9], “RISK STRUCTURES” are considered as an algebraic framework of risk modelling, which is meant to support the design of safe controllers for risk aware machines. Using the concept of risk factor as a primitive modelling tool, such a framework provides equipment for construction, investigation and safeguarding of such controllers. The authors of [9] prove desired algebraic properties of such equipment and show their applicability by using them to specify key aspects of safety control units for autonomous driving and risk-cautious collaborative robots. In order to handle the issue of directional planning in motion planning of autonomous driving, [1] makes use of the global path information by proposing a conditional deep Q-network (DQN) with fuzzy logic. The aim [1] is to make directional planning for an end-to-end autonomous driving systems. In the paper, the architecture of the proposed conditional DQN with fuzzy logic is described. In [23], the design and implementation of a fuzzy logic system for the steering control of autonomous vehicles inside the roundabout is proposed. Cascade architecture for lateral control and parametric trajectory generation are used. Paper [3] presents a model for lane changing in highway driving. It consists of two main parts: threat assessment by assessing the interaction between traffic participants captured in terms of fuzzy logic and a decision making approach based on the concept of Markov Decision Process (MDP). The combined system forms a predictive Fuzzy Markov Decision Process (FMDP). A model predictive control (MPC) scheme for trajectory generation/control complements this decision process. Study [27] aims PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 163 at developing a heterogeneous model of traffic flow which could be used to study the possible influence of connected autonomous vehicles (CAV) on the flow. The authors of the proposed model make use of cellular automata, which had been used to construct a two-state safe-speed model. Notice that the autonomous vehicle (AV) intelligence is not sufficient to solve the complex traffic situations. However, the concept of exclusive traffic lanes bypasses the so far insufficient technology. In [16], the advanced model of cellular automata is used to study the influence of exclusive traffic lanes setting on the traffic flow and stability on highways. Finally, [25] introduces a cellular automaton design for single lane highway sections in order to model automated and human vehicle agents in heterogeneous as well as homogeneous traffic. In our paper we reflect the fact that no matter how precise and accurate HD maps are, autonomous vehicles are not capable of exact copying the suggested trajectory because of effects such as inaccuracies of sensorics, vehicle speed, etc. Instead, they move in its relative vicinity. Therefore we suggest a solution using algebraic hypercompositional structures in which the hyperoperation (or hypercomposition) includes all trajectories acceptable for safe drive. The necessity of such a hyperoperation for modelling the trajectory of the autonomous vehicle is explained in Section 2. In Section 3 we summarize the basic algebraic terminology required to study our model. Our main results are included in Section 4, in which we study the n-ary hyperoperations in the context of HD maps. We also define some new properties of n-ary hypergroupoids which are motivated by the context of trajectories. In Section 5 we shortly summarize our results and outline possiblities of future study such as the use of fractions and n-ary transposition axiom to model trajectories back in time. 2 Motivation Our paper is motivated by the vibrant and so far still ongoing process of development and tailoring HD maps, i.e. high-definition maps, which are being developped as an advanced component and sensor used in the course of movement of autonomous vehicles. These very precise HD maps consist of five layers: base layer,geometric layer,semantic map layer,map priors layer and real-time layer; see [2] for a scheme giving all these layers, or [14, 11, 8] for more details. In spite of the fact that HD maps are intended as high precision map data, the process of their creation is not error-free. The errors, or imprecisions, include global accuracy error such as GPS error, error of localization of the inspection vehicle with recording set for creating the HD maps, local accuracy error caused e.g. by the speed used for recording, accuracy in objects local- PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 164 ization, hardware precision, etc., and local sampling error, i.e. precission of sampling. For details, see [6, 24, 17, 15]. One of the intended purposes of HD maps is to facilitate localization of autonomous vehicles at places with weak GNSS availability. This is an important task assigned to the the first three layers of HD maps. Recall that the remaining two layers, i.e. map priors layer and real-time layer, provide information on real-time traffic such as traffic density, traffic jams, car parks occupancy, etc. As a result, autonomous vehicles process enormous amount of data. This is the reason why elements such as IOT (internet of things) or various cloud storages are considered to be employed in the process. However, it becomes obvious that, when driving, the autonomous vehicle will not have read its planned course in its entirety but will be reading it by parts instead. This implies demands in telecommunication standards of mobile networks. However, not even this means perfection in localization of autonomous vehicles because imprecissions must be still be counted with. Figure 1: Errors is HD maps: a. . . lane width, sv. . . car width, δm. . . HD map error When driving, the autonomous vehicle, represented in the course of its movement and localization by a mass point, moves in a certain band (or strip) induced by the errors suggested in Fig. 1. Therefore, in this paper, we regard algebraic structures which can be used to conveniently model the ideal trajectory of the vehicle taking into account, for safety purposes, its immediate vicinity. Our structures work with an adjustable HD map error δm. Therefore the error already includes car width, which allows us to model a corridor for a safe passage of the autonomous vehicle. Further on, we will write r(disc radius) instead of δm. PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 165 3 Basic notions In this section we collect definitions and trivia regarding concepts that will be used further on. For furher details or properties of the below mentioned notions cf e.g. [4] for a deeper insight and context see overview papers [18, 19]. Notice thatn-ary hypergroups were introduced in [7] and studied e.g. from the point of view n-ary relations, see [5]. Recently, e.g. [22] studied them in the context of composition hyperrings, i.e. hypercompositional structures with two (hyper)operations. Definition 1. Denote by Hnthe Cartesian product H×. . . ×H, where H appears ntimes. A mapping f:Hn−→ P∗(H), where P∗(H)is the power set of Hexcluding the empty set ∅, is called an n-ary hyperoperation (or nary hypercomposition); with nbeing the arity of the hyperoperation. For all x, y ∈Hwe by f(x1, . . . , xn)mean a subset of P∗(H)and by f(A1, . . . , An) the set Sf(x1, . . . , xn)⊆P∗(H), where, for all i= 1, . . . , n, there is xi∈Ai. A non-empty set Hwith an n-ary hyperoperation f:Hn→P∗(H)is called n-ary hypergroupoid and is denoted (H, f). Notation 1. In order to simplify notation, one may use lower and upper indices. Thus one may write f(xn 1)instead of f(x1, . . . , xn)or e.g. f(xi 1, yj i+1, zn j+1), where i<j, instead of f(x1, . . . , xi, yi+1, . . . , yj, zj+1, . . . , zn). However, at most places we prefer not to use this type of notation. Commutativity of n-ary hypergroupoids is not defined while associativity is defined as equality of sets for all possibilities of bracketing elements. Definition 2. By an n-ary semihypergroup we mean an n-ary hypergroupoid (H, f)such that there is f(xi−1 1, f(xn+i−1 i), x2n−1 n+i) = f(xj−1 1, f(xn+j−1 j), x2n−1 n+j) (1) for all i, j ∈ {1,2, . . . , n}and all x1, x2...,x2n−1∈H. n-ary hypergroups can be defined in two different ways – by means of the reproductive law or by means of existence of a solution of equations. We present both alternatives. Definition 3. [7] By an n-ary hypergroup we mean such an n-ary semihypergroup (H, f)in which the equation b∈f(ai−1 1, xi, an i+1) (2) has the solution xi∈Hfor every a1, . . . , ai−1, ai+1, . . . , an, b ∈Hand 1≤i≤ n. PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 166 Remark 1. Notice that, in accordace with Notation 1, by (2) we mean that b is an element of f(a1, . . . , ai−1, xi, ai+1,...an). Remark 2. Alternatively, we may write that n-ary hypergroup is such a n-ary semihypergroup (H, f)that the n-ary reproductive law holds, i.e. that there is f(Hi−1, x, Hn−i) = H(3) for all x∈Hand all i={1,2, . . . , n}. In the context of binary hyperoperations we mention the extensivity of the hyperoperation. Notice that the hyperoperation f:H×H→P(H) is called extensive if, for all a, b ∈H, there is {a, b} ⊆ f(a, b). It is easy to verify that every extensive semihypergroup is a hypergroup. In our paper we work with points in plane. Notice that we denote these as P= [x, y]. 4 Modelling trajectories in HD maps using n-ary hyperstructures Consider discs with center C= [m, n] and perimeter rin real plane, i.e. sets of points discC=[m,n],r ={[x, y]∈R2|(x−m)2+(y−n)2≤r2;m, n ∈R, r ∈R+}.(4) Denote Sdisc the set of all such discs. On Sdisc we define a binary hyperoperation ◦:Sdisc ×Sdisc −→ P∗(Sdisc) by: discA,r ◦discB,r ={discC,r ∈Sdisc |C∈ |AB|} (5) In other words, we fix the perimeter and move the disc along the line segment |AB|from Ato B. The following, rather obvious lemma, will make some of our further considerations more easily explicable. Lemma 1. The set of points induced by discA,r ◦discB,r is convex regardless of A, B or r. Proof. Obvious. Before we proceed, we explain the difference between “◦” defined by (5) and the below hyperoperation “∗” (6) which one might consider as well (and which was, in fact, considered at a very preliminary stage of our research at the 14th Conference on Algebraic Hyperstructures and Applications in 2020; unpublished): PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 167 [x1, y1]∗[x2, y2] = (6) [x, y]; q(x−u)2+ (y−v)2≤r, r ∈R, u ∈tx1+ (1 −t)x2, v ∈ty1+ (1 −t)y2, t ∈ h0,1i If we examine the resulting sets of points in the real plane, the hyperoperations seem to be the same (see the area of A∗B,A◦Bin Fig. 2 and 3). However, they are not because they work with different kinds of objects: points vs discs. Indeed, in “∗” the hyperproduct is defined for points and results in the set of points while “◦” is defined for discs and results in the set of discs. In Fig. 2 we explain why “∗” is only weakly associative and not associative. Assume points A= [x1, y1], B = [x2, y2], C = [x3, y3] and construct (A∗B)∗C. In this case A∗Bis the set of all points of discs with centers on the line segment |AB|. As a result, (A∗B)∗Cwill include points of discs with centers beyond Aand Bwhich will expand the set. However, this expansion will be different for A∗(B∗C) because in B∗Cwe include discs with points beyond Band Cinstead. However, as depicted in Fig. 3, the hyperoperation “◦”is associative because we work with discs with centers in the line respective line segments only (and do not move beyond the points). Figure 2: Weak associativity of “∗” (for clarity reasons circles depicted instead of discs) Further on we will study the properties of (Sdisc,◦). First of all we show that it is a hypergroup. Theorem 1. (Sdisc,◦)is a hypergroup. PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 168 Figure 3: Associativity of “◦” Proof. Proof of associativity is obvious given the considerations above and Fig. 3. Indeed, for all discA,r, discB,r, discC,r, where A= [x1, y1], B= [x2, y2], C= [x3, y3], we have (discA,r ◦discB,r)◦discC,r = =[ D=[x4,y4]∈{[x,y]|x∈x3t+(1−t)u,y∈y3t+(1−t)v,u∈x1l+(1−l)x2,v∈y1l+(1−l)y2,t,l∈[0,1]} discD,r, i.e. the union of all discs on sides and inside the triangle ABC. The calculation for discA,r ◦(discB,r ◦discC,r) is analogous, the sets are obviously equal. The reproductive axiom holds automaticly because the hyperoperation is extensive. From our “Motivation” section it is obvious that the binary hypereoperation of Theorem 1 is not sufficient for modelling the trajectory of autonomous vehicles. In HD maps such vehicles move along curves and follow certain boundaries within which they move. However, the binary operation of Theorem 1 describes movement along line segments only which prevents us to construct reservation fields. If we want to model real-life trajectories, we would have to consider curves instead of straight lines. However, constructing such algebraic (hyper)structures would be complicated. Therefore we will employ n-ary hyperstructures in which curves connecting npoints will be approximated by n−1 line segments as suggested in Fig 4. Next, we denote by Sn disc the Cartesian product Sdisc ×. . . ×Sdisc, where Sdisc appears ntimes. We define the n-ary hyperoperation f:Sn disc → P∗(Sdisc) by: f(discA1,r, . . . , discAn,r) = {discB,r |B∈ |AiAi+1|, i ∈ {1,2,...n−1}} .(7) PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 169 A B C D E F Figure 4: Trajectory: a curve approximated by line segments; the yellow area corresponds to the trace left by the moving disc Such a hyperoperation is obviously suitable for modelling trajectories of an object in a given grid. Moreover, the parameter ris the width of the footprint of the object, or rather the width the object needs to pass its trajectory. Before giving a theorem for such an n-ary case, we recall one definition and include two simple lemmas which will facilitate our proof of associativity. Definition 4. Let (H, f)be an n-ary hypergroupoid. If there is {a1, . . . , an} ⊆ f(a1, . . . , an)for all (a1, . . . , an)∈Hn, we say that H, or f, is extensive. Lemma 2. Sets f(discA1,r, . . . , discAn,r)depend on the order of points A1,...An. Proof. Obvious, see Fig. 4. Lemma 3. For hyperoperation fdefined by (7) there is f(discA1,r, . . . , discAn,r) = (8) =discA1,r ◦discA2,r ∪discA2,r ◦discA3,r ∪. . . ∪discAn−1,r ◦discAn,r. Proof. It can be easily seen that the result of the n-ary hyperoperation fis the union of discs with circles on the broken line where the endpoint of each line segment is the starting point of the following line segment. Theorem 2. For all n > 2, the pair (Sdisc, f), where f:Sn disc →P∗(Sdisc), is an n-ary hypergroup. Proof. The associativity axiom holds – it is obvious thanks to Theorem 1 and Lemma 3. Out of reasons analogous to the binary case, the reproductive axiom follows from the extensivity of f. The fact that (Sdisc, f) is, for an arbitrary arity n, extensive, is obvious. PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 176 [2] K. Chellapilla, Rethinking aps for self-driving, [online] https://medium.com/lyftself-driving/https-medium-com-lyftlevel5rethinking-maps-for-self-driving-a147c24758d6 [3] S. Coskun, R. Langari, ”Predictive Fuzzy Markov Decision Strategy for Autonomous Driving in Highways”, In IEEE Conference on Control Technology and Applications (CCTA), 2018, pp. 1032-1039, doi: 10.1109/CCTA.2018.8511369. [4] P. Corsini, V. Leoreanu, Applications of Hyperstructure Theory; Kluwer Academic Publishers: Dodrecht – Boston – London, 2003. [5] I. Cristea, M. S¸tefanescu, Hypergroups and n-ary relations, European J. Combin.,31(3) (2010), 780-789. [6] T. Dahlstrom, How Accurate Are HD Maps for Autonomous Driving and ADAS Simulation? [online] https://news.atlatec.de/how-accurate-are-hd-maps-for-autonomousdriving-and-adas-simulation/ 2020. [7] B. Davvaz, T. Vougiouklis, n–ary hypergroups, Iran. J. Sci. Technol. Trans. A-Sci.,30(A2) (2006), 165–174. [8] T. Dias, J. Ribeiro, L. Moura, D. Juregui, M. Miranda, J. Almeida, M. Jooriah, HD Maps in the 5G-MOBIX project, IEEE 5G for CAM Summit, 2021. [9] M. Gleirscher, R. Calinescu, J. Woodcock, RISKSTRUCTURES: A design algebra for risk-aware machines. Form. Asp. Comp. (2021). doi: 10.1007/s00165-021-00545-4. [10] M. Hamdi, N. Boudriga, Algebraic specification of network security risk management. In Proceedings of the 2003 ACM workshop on Formal methods in security engineering (FMSE ’03), Association for Computing Machinery, New York, NY, USA, 2003, doi:https://doi.org/10.1145/1035429.1035435. [11] C. Kim, S. Cho, M. Sunwoo, K. Jo, Crowd-Sourced Mapping of New Feature Layer for High-Definition Map. Sensors.18(2018)(12), 4172. [12] ˇ S. Kˇrehl´ık, n-ary Cartesian Composition of Multiautomata with Internal Link for Autonomous Control of Lane Shifting. Mathematics 2020,8(5), 835 PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 177 [13] ˇ S. Kˇrehl´ık, J. Vyroubalov´a, The Symmetry of Lower and Upper Approximations, Determined by a Cyclic Hypergroup, Applicable in Control Theory, Symmetry 12(2020),(1) 54. [14] S. Liu, L. Li, J. Tang, S. Wu, J-L. Gaaudiot, Creating Autonomous Vehicle Systems, Morgan & Claypool, 2018. [15] R. Liu, J. Wang, B. Zhang, High Definition Map for Automated Driving: Overview and Analysis. Journal of Navigation, 73(2020)(2), 324-341. [16] K. Ma, H. Wang, A Cellular Automaton Model Considering the Exclusive Lanes of Autonomous Vehicles on Expressway, In CICTP 2019: Transportation in China: Connecting the World, 2019, doi:10.1061/9780784482292.477. [17] L. Ma, Y. Li, J. Li, Z. Zhong, M. A. Chapman, Generation of horizontally curved driving lines in HD maps using mobile laser scanning point clouds, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,12(2019)(5), 1572-1586. [18] Ch. Massouros, G. Massouros, An Overview of the Foundations of the Hypergroup Theory, Mathematics 2021,9(9), 1014. [19] Ch. Massouros, G. Massouros, Hypercompositional Algebra, Computer Science and Geometry, Mathematics 2020,8(8), 138. [20] S. Mirvakili, (i,j)-transposition n-ary hypergroups, In The Extended Abstracts of Posters of The 44th Annual Iranian Mathematics Conference, 27-30 August 2013, Ferdowsi University of Mashad, Iran, pp. 141-144. [21] S. Mirvakili, B. Davvaz, On some combinatorial aspects of transposition n-ary hypergroups, Carpathian J. Math.,30(2014)(1), 109–116. [22] M. Norouzi, I. Cristea, Hyperrings with n-ary composition hyperoperation, J. Alg. Appl.,17(2) (2018), 1850022. [23] J. P. Rastelli, M. S. Penas, Fuzzy logic steering control of autonomous vehicles inside roundabouts, Appl. Soft Comput. 35(2015), 662-669. [24] Toyota Research Institute – Advanced Development, Inc., TRI-AD enables successful creation of HD maps for automated driving on surface roads, [online] https://global.toyota/en/newsroom/corporate/31898884.html, 2020. PROPERTIES OF N-ARY HYPERGROUPS RELEVANT FOR MODELLING TRAJECTORIES IN HD MAPS 178 [25] T. Vranken, B. Sliwa, C. Wietfeld, M. Schreckenberg, Adapting a cellular automata model to describe heterogeneous traffic with human-driven, automated, and communicating automated vehicles, Physica A: Statistical Mechanics and its Applications,570(2021), 125792. [26] L. Wan, Y. Sun, L. Sun, Z. Ning and J. J. P. C. Rodrigues, “Deep Learning Based Autonomous Vehicle Super Resolution DOA Estimation for Safety Driving,” In IEEE Transactions on Intelligent Transportation Systems, doi: 10.1109/TITS.2020.3009223. [27] L. Ye, T. Yamamoto, Modeling connected and autonomous vehicles in heterogeneous traffic flow, Physica A: Statistical Mechanics and its Applications,490(2018), 269-277. ˇ Stˇep´an Kˇ REHL´ IK, CDV – Transport Research Centre L´ıˇseˇnsk´a 33a, 636 00 Brno, Czech Republic Email: [email protected] Michal NOV´ AK, Faculty of Electrical Engineering and Communication Brno University of Technology Technick´a 8, 616 00 Brno, Czech Republic Email: nov[email protected] Melis BOLAT, Department of Mathematics, Faculty of Arts and Sciences Yildiz Technical University 34220 Esenler, Istanbul, Turkey Email: melisb[email protected]