Keywords: Human-Robot Interaction, Navigation, Human-Robot Motion, Human-Robot Collaboration, Effort Distribution, Collision Avoidance, Near-Symmetry scenarios ORCA Optimal Reciprocal Collision Avoidance. 53, 54 ROS Robot Operating System. 76, 77 RPROP Resilient Propagation. 48

Classical approaches for robot navigation among people have focused on guaranteed collisionfree motion with the assumption that people are either static or moving obstacles. However, people are not ordinary obstacles. People react to the presence and the motion of a robot. In this context, a robot that behaves in human-like manner has been shown to reduce overall cognitive effort for nearby people as they do not have to actively think about a robot's intentions while moving on its proximity.

Our work is focused on replicating a characteristic of human-human interaction during collision avoidance that is the mutual sharing of effort to avoid a collision. Based on hundreds of situations where two people have crossing trajectories, we determined how total effort is shared between agents depending on several factors of the interaction such as crossing angle and time to collision. As a proof of concept our generated model is integrated into Reciprocal Velocity Obstacles (RVO). For validation, the trajectories generated by our approach are compared to the standard RVO and to our dataset of people with crossing trajectories.

Collaboration during collision avoidance is not without its potential negative consequences. For effective collaboration both agents have to pass each other on the same side. However, whenever the decision of which side collision should be avoided from is not consistent for people, the robot should also account for the risk that both agents will attempt to incorrectly cross each other on different sides. Our work first determines the uncertainty around this decision for people. Based on this, a collision avoidance approach is proposed so that, even if agents initially choose to incorrectly attempt to cross each other on different sides, the robot and the person would be able to perceive the side from which collision should be avoided in their following collision avoidance action. To validate our approach, several distinct scenarios where the crossing side decision is ambiguous are presented alongside collision avoidance trajectories generated by our approach in such scenarios.

Résumé

Ces dernières années, la tendance des robots capables de partager des espaces domestiques ou de travail avec des personnes a connu une croissance importante. Du robot guide à l'aspirateur autonome, ces robots dits "de service" sont de plus en plus intégrés dans la vie quotidienne des profanes.

Bien que les progrès des logiciels et du matériel aient permis un comportement plus intelligent et plus autonome des robots, la présence plus répandue des robots parmi les gens pose un nouvel ensemble de défis pour la communauté scientifique. Même si les gens ne sont pas que des obstacles ordinaires, les approches classiques de navigation se sont concentrées sur la garantie d'un mouvement sans collision en supposant que les gens sont soit des obstacles statiques, soit des obstacles en mouvement.

Traiter les gens comme des obstacles ordinaires signifie qu'un robot est incapable de tenir compte de la réaction d'une personne au mouvement du robot. Pour cette raison, un mouvement donné d'un robot peut être perçu comme dangereux ou inhabituel, ce qui incite les gens à adopter un mouvement plus prudent pendant qu'ils réfléchissent activement aux intentions du robot.

Dans ce contexte, notre travail se concentre sur la manière dont un robot doit se déplacer au milieu des gens, ce qu'on appelle un problème de Mouvement homme-robot. Plus précisément, nous nous concentrons sur la reproduction d'une caractéristique de l'interaction homme-homme lors de la prévention des collisions, à savoir le partage mutuel des adaptations effectuées pour résoudre une collision.

Etant donné que les situations d'évitement des collisions entre les personnes sont résolues en coopération, cette thèse modélise la manière dont cette coopération se fait afin qu'un robot puisse reproduire leur comportement. Pour ce faire, des centaines de situations où deux personnes ont des trajectoires de croisement ont été analysées. À partir de ces trajectoires humaines impliquant une tâche d'évitement des collisions, nous avons déterminé comment l'effort total est partagé entre chaque agent en fonction de plusieurs facteurs de l'interaction tels que l'angle de croisement, le temps avant collision ainsi que la vitesse. Pour valider notre approche, une preuve de concept est intégrée dans le framework Robot Operating System (ROS) utilisant une version modifiée de Reciprocal Velocity Objects (RVO) afin de répartir l'effort d'évitement des collisions de façon humanoïde.

Bien que la modélisation de la manière dont un robot devrait collaborer avec des personnes ait fourni une base de référence importante pour le comportement d'évitement des collisions, la collaboration pendant une collision pourrait éventuellement engendrer de conséquences négatives. En particulier, pour assurer une collaboration efficace lors de la prévention des collisions, il est necessaire de prévoir si la personne tentera d'éviter la collision en passant du côté gauche ou du côté droit, c'est-à-dire en prenant une décision de classe homotopie. Cependant, à situation ou cette décision de classe d'homotopie n'est pas cohérente pour les gens, le robot est obligé de tenir compte de la possibilité que les deux agents tentent de se croiser d'un côté ou de l'autre et prennent une décision nuisible à la prévention des collisions.

Ainsi, dans cette thèse, nous évaluons également ce qui détermine la frontière qui sépare la décision d'éviter la collision d'un côté ou de l'autre. En faisant une approximation de l'incertitude entourant cette limite, nous avons élaboré une stratégie d'évitement des collisions qui tente de résoudre ce problème. Notre approche est basée sur l'idée que le robot doit planifier son mouvement d'évitement des collisions de telle sorte que, même si les agents, dans un premier temps, choisissent à tort de se croiser sur des côtés différents, le robot et la personne soient capables de percevoir sans ambiguïté la bonne décision de classe d'homotopie sur leur action suivante.

Mots-clés: Interaction homme-robot, Navigation, Mouvement homme-robot, Collaboration homme-robot, Distribution de l'effort, Évitement des collisions, Scénarios de quasisymétrie A special thanks goes to my labmate and, most importantly, friend Khansa Rekik for bringing positive energy and deep scientific discussions throughout this journey.

To my family for the continued support and everlasting patience, thank you, I owe this work to all of you.

For those in the Pervasive team who supported me throughout the hardships -thank you. A special thanks to Alexandra Fitzgerald for the positive attitude and impeccable work ethic and Nashwa Abubakr for all discussions and, most importantly, friendship.

Immeasurable gratitude goes to my PhD advisor James Crowley for providing me perspective whenever I needed it the most. I also would like to apologize for the negative impact of my thesis review on your vacations -but I do appreciate it. Thanks for everything.

For my friends from Chroma and lunch irmãos, hermanos and bhai thank you. I would not have been able to progress as much in my scientific career without our discussions about state of the art techniques. Also for letting me win at baby foot.

For my unforgettable friends, professors and advisors from both ACSO/BRT and UNEb, my sincere thanks. The memories of our work and victories together as an unified group on conferences, programming competitions, RoboCup challenges and so many other events, allowed me to reach further than I ever would have without all of you.

For both teaching me how to manage academic problems and engage in effective academic discussion, I would also like to thank Leizer Schnitman. I carry those lessons with me.

A warm thank you to all the members of the laboratory Mouvement, Sport, Santé (M2S) for the two insightful weeks of collaboration in-site. A special appreciation to Anne-Hélène Olivier and Julien Pettré for the continued support afterwards.

Finally, I would like to offer a special thanks to my undergraduate professor Jorge Farias, who is no longer with us, but served as an academic and personal role model. His passion and dedication to scientific discovery has inspired me follow an academic career. A comparison between a standard approach and our approach when two virtual agents attempt to avoid collision with each other in a near-symmetry situation in which one agent misjudges his crossing order. Let ∆v x and ∆v y be a change in velocity in x and y axis. . . . . . . . . . . . . . . . . . . . . 6-7 Comparison of ideal scenarios where people always respect crossing order to our approach where ineffective collaboration is possible. . . . . . . . . . [START_REF] Basili | Strategies of locomotor collision avoidance[END_REF][START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF][START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF] Several examples of MPDH where agents misjudge crossing order. . . . . . C-1 Area of interest is the right triangle with two sides of length ℒκ . . . . . GLM Generalized Linear Model. [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF][START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF]70,72,99,105 HRM Human Robot Motion. 22,[START_REF] Mombaur | From human to humanoid locomotion-an inverse optimal control approach[END_REF]39,40,46,48,49,51 M2S Mouvement,Sport,Santé. 20,[START_REF] Mombaur | From human to humanoid locomotion-an inverse optimal control approach[END_REF]61,86,99 MPD Minimum Predicted Distance. [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF][START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF]28,29,30,34,70,82,83,84,85 MPDH Minimum Predicted Distance with Goal Heading. 83

List of Figures

List of Tables

Chapter 1

Introduction

"Models are useful distillations of reality. Although wrong by definition, they are the wind that blows away the fog and cuts through the untamed masses of data to let us see answers to our questions." -Dana K. Keller

Classical approaches in robotics attempt to guarantee safe robot motion in the presence of static [START_REF] Crowley | Navigation for an intelligent mobile robot[END_REF] and moving obstacles [START_REF] Quinlan | Elastic bands: Connecting path planning and control[END_REF]. However, treating people as ordinary obstacles can have unintended negative consequences. Notably, not respecting social norms and expectations can cause people to perceive a robot behavior as unsafe or unnatural. Even behaviors that appear polite at a glance, such as a robot yielding to a person in a crossing scenario, may violate expectations of nearby people. A robot should not always yield, it must understand what is the expectation of people for the robot in a given situation and plan motions that respect this expectation.

This thesis reports on the effort to examine this problem as a problem of collaboration. Within this context, this chapter introduces our research problem statement. Moreover, our contributions and publications are also highlighted followed by the content organization of the following chapters of this document.

Collaborative collision avoidance

A robot that behaves in a more human-like manner has been shown to reduce global cognitive effort for people in the environment [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF]. Ideally, a robot that moves in a manner indistinguishable from a fully aware and benevolent person would inspire a more relaxed behavior from people, in other words, people would be less concerned with the likely robot motions. Such natural motion would help make robots more acceptable to people. This would reduce the discomfort caused by the robot within spaces that require interaction with people, such as navigation in homes [START_REF] Cosgun | Anticipatory robot path planning in human environments[END_REF][START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], in crowded environments [START_REF] Bohórquez | Adaptive step rotation in biped walking[END_REF][START_REF] Trautman | Unfreezing the robot: Navigation in dense, interacting crowds[END_REF][START_REF] Shiomi | Towards a socially acceptable collision avoidance for a mobile robot navigating among pedestrians using a pedestrian model[END_REF][START_REF] Triebel | A socially aware service robot for passenger guidance and help in busy airports[END_REF] and in unknown environments [START_REF] Koenig | Improved fast replanning for robot navigation in unknown terrain[END_REF][START_REF] Dolgov | Path planning for autonomous vehicles in unknown semi-structured environments[END_REF].

Despite the potential benefits of human-like collision avoidance, many classical and state of the art approaches assume that the person behaves as a moving obstacle. For instance, in [START_REF] Bohórquez | Adaptive step rotation in biped walking[END_REF] a footstep planner for a bipedal walking robot was able to efficiently navigate within crowds but with the assumption that people always preserve their original velocity with no regard for the chosen robot motion. In contrast, our work attempts to find a compromise between guaranteed safe navigation and navigation that is perceived as safe and natural by nearby people.

Based on a dataset of people in dyadic collision avoidance situations which is the result of a collaboration with the laboratory Mouvement, Sport, Santé (M2S), this thesis is concentrated on imitating the manner in which people avoid collision with each other. More specifically, our focus is on allowing a robot in dyadic collision avoidance situation with a person to replicate the usual impact of collision avoidance in both time to the goal and energy expenditure, what we define in our work as collision avoidance effort, based on situational factors that describe a collision situation, such as crossing order.

Crossing order represents the order in which agents reach the intersection between their trajectories. In practice, such ordering indicates that one person is crossing in front and the other person is crossing behind. Crossing in front or behind another person has been shown to affect the manner in which people avoid collisions with each other [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF] and were also shown to be strongly correlated to the value of the derivative of the bearing angle at the start of collision avoidance [START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF].

Although the distribution of motion adaptations based on crossing order is an important aspect of human motion, it is nonetheless not sufficient to reproduce collision avoidance behavior of people. For instance, people have been shown to sometimes reverse their crossing order when collision avoidance starts [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF] even though that can entail longer time to avoid collision [START_REF] Vassallo | How do walkers behave when crossing the way of a mobile robot that replicates human interaction rules?[END_REF].

Our dataset of people in dyadic collision avoidance situations shows that crossing order reversals are more frequent whenever the amount of convergence or divergence of the obstacle to the center of the field of view of a person is negligible -what we call near symmetry situations. As a consequence, as shown in Fig. 1-1a and 1-1b, the boundary between the decision to cross before or after another person (or from the left or right side in case of head-on collision) becomes less evident.

When crossing order is not evident it is possible that people initially attempt to avoid collision while incorrectly choosing the same crossing order. In this thesis we also present a collision avoidance approach to reduce the negative impact of this ineffective collaboration in the collision avoidance. That is, we intend to plan collision avoidance motions in such a way that minimizes the amount of time both agents remain with an ambiguous crossing order.

Our objective is to formalize a robot collision avoidance behavior as a collaborative task while accounting for and mitigating ineffective collaboration. This would allow people to act more naturally towards a robot. This approach is inline with recent results in social sciences studies, where people are shown to be more cautious around a robot that does not respect social norms [START_REF] Vassallo | How do walkers avoid a mobile robot crossing their way?[END_REF] while people react more naturally when they know that a robot behaves in a human-like manner [START_REF] Vassallo | How do walkers behave when crossing the way of a mobile robot that replicates human interaction rules?[END_REF].

Our objective is to develop a collision avoidance algorithm that can 1. Predict, based on situational factors, the expected distribution of motion adaptations between agents during dyadic collision avoidance.

2. Determine, at a given instant, whether an agent will choose to cross first or last in a collision avoidance scenario and the uncertainty associated with this decision 3. Develop a human-like collision avoidance approach for a robot in order minimize the amount of time in a near-symmetry scenario, reducing the amount of time in which ineffective collaboration is possible.

Contributions

1. A model for asymmetric distribution of motion adaptations between a robot and a person during collision avoidance. Our model does not attempt to share collision avoidance effort equally or to simply minimize the combined amount of motion adaptations, instead, it predicts the amount of collision avoidance effort a person would have been expected to invest to avoid a future collision in a given scenario. This prediction can then be used to change the collision avoidance behavior of existing navigation approaches.

2.

Collision avoidance approach that accounts for the potential uncertainty in crossing order determination and mitigates its potential negative consequences. We approximate the uncertainty over a person's decision to cross first or last in a given scenario. Based on this uncertainty, our collision avoidance approach minimizes ineffective collaboration by adapting the collision avoidance behavior of a robot in tandem with the uncertainty over crossing order. Our approach guarantees with a certain confidence that even if agents initially assume the same crossing order they will be more likely to perceive the correct crossing order in their next decision step.

Thesis Structure Chapter 2 -Collision avoidance between people

There is abundant literature in the domain of social sciences that discusses and analyzes human behavior during collision avoidance. Chapter 2 draws on this literature to describe concepts for characterizing the temporal evolution of a collision scenario between two people and the impact of different initial conditions on the decision making of a person. The impact of different initial conditions is evaluated with respect to both situation-specific factors (position, velocity, etc.) and person-specific factors (such as age and gender). The manner in which these factors affect role selection, that is, whether a person will cross in front or behind another person, is also presented alongside a discussion about situations where people change their original roles (role reversals). Furthermore, the concept of homotopy class is also presented and its differences with respect to the concept of crossing order are specified. Finally, in our closing remarks a discussion is made on how situational factors could be used to predict the manner in which people distribute motion adaptations to avoid collision and also about the potential negative impact of role reversals in collision avoidance.

Chapter 3 -State of the art in Human-Robot Motion This chapter reviews the state of the art in Human Robot Motion (HRM). Before the discussion of specific approaches, the concept of (dis)comfort is presented in order to aggregate similar terms used throughout the literature. Based on our definition of comfort, state of the art works in HRM are divided into three categories. First, approaches are presented that deal with comfort in the domain of social spaces and its sub-categories: personal, interaction, activity and affordance spaces. Second, the literature on concepts such as legibility, visibility and attention is presented and their impact on comfort is also discussed. Third, a number of human-aware collision avoidance approaches are discussed involving both human-like models, such as the Social Force Model, and approaches that attempt to minimize discomfort-like measures during motion planning. Moreover, recent approaches that attempt to avoid the potential of future collision by following the flow of people are also discussed. In our final remarks, the focus of our work in collaboration between people during collision avoidance is established within the context of human-aware collision avoidance.

Chapter 4 -Literature on collaboration during collision avoidance

This chapter reviews previous research on the problem of collaboration during collision avoidance. Five techniques that address this problem are presented and discussed. These techniques are divided in two categories: reactive and planning-based. Reactive approaches, such as Reciprocal Velocity Obstacles, are discussed with respect to their strategy for collaboration during collision avoidance. Planning-based approaches based on minimization of discomfort and on learning from human trajectories are described. Finally, a detailed comparison of features found in each of the examined approaches is presented and compared to our work. In this comparison our work was found to be one of the few works that imitate the distribution of motion adaptations used by people to avoid collision and the only work that dealt with the explicit detection and mitigation of situations with unclear roles between agents.

Chapter 5 -Effort distribution during collision avoidance

Our first contribution, introduced in this chapter, presents a model to imitate the manner in which people collaborate to avoid future collision. To that end, we first describe our dataset created in collaboration with the laboratory Mouvement, Sport, Santé. In order to evaluate human behavior within this dataset, a novel cost function is presented based on the impact on both energy and time to the goal of a person due to collision avoidance. This cost function is then applied within our dataset in order to shown, in a statistically significant manner, that there is a difference in the distribution of effort between roles. Based on these results, a number of situation specific factors at the start of collision avoidance are used as a predictor of collision avoidance effort and its distribution among agents. This predictor is then implemented into the navigation approach named Reciprocal Velocity Obstacles in order to allow for more human-like behavior and also to validate the developed predictor.

For validation a comparison between standard Reciprocal Velocity Obstacles, our approach and the baseline behavior obtained from our dataset is made. Our approach better imitated human behavior in most of the evaluated cases while its main limitation was being unable to replicate role reversals.

Chapter 6 -Human-robot collision avoidance under near symmetry

Our second contribution is presented in this chapter, which attempts to mitigate potential negative consequences of collaborative collision avoidance when crossing order between agents is either ambiguous or undefined. First, an extension of the Minimum Predicted Distance is presented in order to better visualize the negative impact of crossing order ambiguity in the trajectories of people. Based on evaluation of our dataset, the boundary that separates the choice of role for a given agent is specified based on the derivative of the bearing angle. This boundary allows our model to predict the role uncertainty of a given scenario for nearby people. Our approach exploits properties of uniform distributions in order to guarantee, with a certain confidence, that even if agents initially choose the same role they will be able to perceive the correct role in the next time step. Finally, validation of our collision avoidance approach is presented over several distinct scenarios and compared to Reciprocal Velocity Obstacles, a method that is unable to misjudge crossing order.

The main benefit of our approach is reducing the amount of time agents remain in a situation with ambiguous crossing order as a consequence of ineffective collaboration between agents due to ambiguous crossing order.

Chapter 7 -Conclusion

The closing chapter of the thesis provides a general overview of our work. Additionally, a detailed review of our contributions and the limitations of the current iteration of our approach are presented. Its final section presents possible perspectives for our work, such as evaluating our approach in virtual reality, accounting for robot-robot scenarios and experiments with multiple people.

used within Chapter 5 in order to learn the distribution of effort from trajectories of people.

Chapter 2

Collision avoidance between people This chapter describes some of the most relevant concepts for characterizing a collision situation, and describes the impact of different initial conditions of interaction during such a task on the decision making of a person. These concepts relate to both situation-specific and person-specific characteristics of a collision avoidance scenario. This allows us to build foundations to the design of "human-like" robot behavior when avoiding a collision with people.

Collision avoidance behavior

People have been shown to predict the risk of future collision and to react appropriately to reduce such risk using motion adaptations [START_REF] Olivier | Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers[END_REF]. Collision risk represents the perception of people that their distance to a given obstacle will be smaller than an ac-

Human behavior

(a) Collision avoidance situation between two people. ceptable threshold in the future. This threshold was also found to encompass their personal space1 .

The bounds of the time interval in which agents recognize each other up until the time in which minimum distance between agents is reached represents the interaction phase [START_REF] Olivier | Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers[END_REF]. As shown in Fig. 2-1, interaction begun at the moment the walls no longer occluded people from seeing each other. Moreover, interaction ended when distance between people reached its smallest value. A detailed visual breakdown of the interaction phase is presented in the Sec. 2.1.1. In order to properly characterize the behavior of people during interaction in this section, we recall a standard measure, the Minimum Predicted Distance (MPD), that calculates the future distance of closest approach between people [START_REF] Olivier | Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers[END_REF]. We describe how the temporal evolution of MPD during interaction between people is used in the literature to describe collision avoidance progress. In Sec. 2.1.3 we discuss several factors that can impact the behavior of people during the interaction phase.

Minimum predicted distance

Collision avoidance progress can be measured in terms of the MPD between people. This variable is presented in the literature as the minimum distance people would reach in the future in case no motion adaptations are performed and is defined as

MPD(t) = ∞ min l=t ‖( p r (t) + v r (t) • (l -t)) -( p p (t) + v p (t) • (l -t))‖ (2.1)
where p r (t) and p p (t) represent, respectively, the current position of an agent r and p at time t. In the same manner, v r (t) and v p (t) represent, respectively, the velocity of agent r and p at time t and ‖•‖ denotes the euclidean distance.

Whenever the minimum predicted distance is smaller than a certain threshold this indicates a future collision will happen if agents do no shift their motion. For people, collision risk was generally perceived as high enough to justify collision avoidance motions whenever their MPD was at most one meter [START_REF] Olivier | Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers[END_REF]. Thus, whenever people are at a certain distance from each other and MPD is below a certain threshold, people adapt their motion in order avoid collision -increasing the value of MPD.

The MPD provides a numerical representation of collision risk and also collision avoidance progression.

Phases of collision avoidance during interaction

The temporal evolution of MPD during collision avoidance among people allowed social science studies to decompose interaction between people into three successive phases: observation, reaction and regulation [START_REF] Olivier | Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers[END_REF]. These phases can be summarily described as:

1. Observation during which the possibility of a collision situation is recognised, prior to motion adaptation. During this phase, the MPD does not change.

2. Reaction phase includes most of the actual motion to avoid the collision, where agents choose motion adaptations that increase the MPD above a certain margin that avoids collision and preserves personal space between agents;

3. Regulation is the phase where the agent maintains the MPD at a stable value without collision risk until minimum distance is reached.

This division is based on the temporal evolution of MPD in reaction to the motion adaptations done to avoid collision [START_REF] Olivier | Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers[END_REF]. All the aforementioned phases can be observed in Fig. 2-2 which breaks down the behavior of MPD at the start of the interaction until after the end.

The observation phase has a short duration as people were found to be able to efficiently detect a potential future collision risk a single step after seeing a moving obstacle ( [START_REF] Gérin-Lajoie | The negotiation of stationary and moving obstructions during walking: anticipatory locomotor adaptations and preservation of personal space[END_REF]. The phase with longest duration, referred as reaction phase, is responsible for the increase in MPD. Collision avoidance and its associated motion adaptations start from this phase. Finally, the regulation phase represents the final phase of the interaction. In this phase, MPD remains constant until the minimum distance between agents is reached. After the interaction, in the absence of additional obstacles, the MPD continues to increase as agents move further away from each other.

Personal and situational factors impact on interaction

The behavior of people during interaction is determined by several factors. These factors are generally subdivided into two categories, the situational factors (such as speed, heading and crossing angle) and personal factors (such as height or gender).

Recent studies concerning the manner in which people adapt their motion to avoid a collision between each other, such as [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF], observed that situational factors are more important than personal factors for explaining behavior during collision avoidance. In this subsection, we discuss both situational and personal factors and their impact on people's behavior based on existing literature.

Personal factors

Personal factors represent person-specific characteristics [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF], such as age, height and gender. These factors have been shown to have an impact on interpersonal coordination during interaction.

One such impact was observed in [START_REF] Van Basten | Exploiting motion capture to enhance avoidance behaviour in games[END_REF] during head-on collision avoidance trials, where gender distribution in a group of people affected their degree of collaboration. In particular, in their dataset two males collaborated less than two females to avoid future collision. Moreover, the minimum clearance between a pair of males was smaller than between two people with different genders. Another interesting observation was that one short person and one tall person collaborate less than two short people.

The degree of collaboration during collision avoidance is not the only potential impact of personal factors in human behavior during motion. In [START_REF] Costa | Interpersonal distances in group walking[END_REF], the gender distribution within a group of people had an influence in group organization. Groups of males in forward motion were more likely to be further apart than both mixed groups and female groups. This was seen in both dyads and triads, however, this pattern did not generalize to larger groups. Moreover, it was found that groups with significant height difference walked abreast less often than groups with similar height.

In [START_REF] Vallis | Children use different anticipatory control strategies than adults to circumvent an obstacle in the travel path[END_REF], during interaction with static obstacles it was found that children avoid collision differently from adults. More specifically, children rely more on visual information in comparison to adults in order to increase accuracy. In addition, children were found to choose different change in travel direction to avoid collision, this is caused by several factors including a greater role of foot placement for control of center of mass deviation.

Situational factors

Situational factors are based on situation-specific characteristics, such as position, heading and speed. The importance of situational factors for successful collision avoidance was shown in [START_REF] Basili | Strategies of locomotor collision avoidance[END_REF][START_REF] Huber | Adjustments of speed and path when avoiding collisions with another pedestrian[END_REF], where depending on the crossing angle and the available space, people adapted walking speed and/or walking path to avoid collision. Moreover, several existing methods that replicate behavior of people (obtained from empirical data) are only able to do so when situational factors are taken into account [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF][START_REF] Moussaïd | How simple rules determine pedestrian behavior and crowd disasters[END_REF].

Among the situational factors that influence the type and amount of motion adaptations for people, we list:

• Time to collision (also known as time to contact) (Alenyà et al., 2009) affects the perceived risk of collision which can have a substantial impact on motion adaptations.

• Initial crossing order, which is calculated before start of the collision avoidance, can determine the behavior of an agent with respect to distribution of motion adaptations [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF].

• Bearing angle represents the position of another person in one's field of view and can impact collision avoidance behavior. For instance, a person walking behind another person generally does not to expect the person in front to contribute to collision avoidance. Discussed in detail in Sec. 2.2.1.

• Derivative of the bearing angle: this situational factor was found to reliably predict future collision. Whenever agents are approaching each other and the derivative of the bearing angle is equal to zero a collision is inevitable. Furthermore, the value of the derivative of bearing angle can also predict crossing order depending on whether the object is diverging or converging from the gaze axis (center of the field of view). This is discussed in detail in Sec. 2.2.1.

• Speed of people: the speed in which a person walks has a strong relationship with their derivative of the bearing angle. However, the difference in speed between people may also have an impact on collision avoidance. For instance, it is important to evaluate the impact of a person going much faster than another one in the distribution of motion adaptations to avoid collision.

• Crossing angle has been shown to affect the choice between adapting speed and/or walking path [START_REF] Basili | Strategies of locomotor collision avoidance[END_REF][START_REF] Huber | Adjustments of speed and path when avoiding collisions with another pedestrian[END_REF].

Roles during collision avoidance

During the observation phase, people perceive their role in a future collision situation as either crossing in front or behind. In general terms, these roles define the type of motion adaptation one must perform to avoid future collision in a collaborative manner [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF]. The person crossing in front role generally chooses to accelerate while also changing heading, while the person crossing behind usually decelerates while also changing heading.

A recent work found that there is a difference in the amount of motion adaptations done by the person crossing in front and the person crossing behind [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF], their findings indicate that, in average, the person crossing behind contributes more to collision avoidance than the person crossing in front. Given the change in behavior depending on a person's role, in this section, we describe what factors were found to predict the perceived crossing order of an agent. This allow us to understand how to predict and replicate human behavior in a more realistic fashion.

Predicting the role of a person during collision avoidance

Several works have studied the manner in which one can predict the role of a person during collision avoidance. In [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF], one experiment was executed to predict crossing order from speed and heading (velocity) for each agent before motion adaptations started occurring. They were able to estimate with 93% accuracy the future role of each agent 2.5 meters before participants crossed each other. In other words, in the large majority of the cases, crossing order was defined early and did not change. According to [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF], correctly predicting the role of people depends on whether both pedestrians are able to predict the order in which their intersection will be reached.

Crossing order decision can be explained in terms of the visual stimuli of the agents [START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF], where

• the person crossing in front sees the person crossing behind diverge from the center of its field of view (bearing angle goes away from zero) as the time to collision diminishes,

• while the person crossing behind sees the person crossing in front converging towards the center of its field of view (bearing angle approaches zero).

Both the person crossing in front and behind can be visualized in Fig. 2-3a.

Determining the role of an agent before motion adaptations is important in order to properly understand and replicate human behaviour. In [START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF], the derivative of bearing angle was found to correctly predict future collision and its sign was found to be a reliable indicator of future crossing order. The bearing angle denotes the angle between the heading of an agent and another obstacle (dynamic or otherwise). In order to calculate the value of the derivative of the bearing angle, let r and p represent a robot and a person respectively. From the local coordinate space of the robot r, the bearing angle to p is defined as α r,p (t) = atan2(y, x) where, for brevity, we define x = x p (t) and y = y p (t). The total derivative2 of α r,p (t) is then defined as αr,p (t) = y x 2 + y 2 dx +

x x 2 + y 2 dy , (2.2)
where x r (t) and y r (t) represent the x and y position of agent r at time t. A visual representation of the bearing angle, from the local coordinate space of a robot, and its derivative (0,0)

α (t) α (t)
.

Role reversal in the literature

In the context of collision avoidance, role reversal refers to the change of role between agents after the start of the collision avoidance. This means that although one agent was predicted to pass in front and the other behind during collision avoidance, during the actual collision avoidance their roles were swapped. In practice, this means that during role reversal the MPD between agents first decreases (due to change of role) and then increases until collision avoidance is completed.

In [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF], using solely the speed and heading of each agent they were able to predict the crossing order with 93% accuracy. This means that role reversals happened in only 7% of the cases observed. This is likely due to the fact that role reversals are generally a less time-efficient way to solve collision avoidance particularly when roles are defined and well perceived.

For proper visualization of role reversal in collision avoidance scenarios, a modified version of MPD was proposed in [START_REF] Vassallo | How do walkers avoid a mobile robot crossing their way?[END_REF]. In this version, named Signed Minimum Predicted Distance (SMPD), the person crossing in front has a positive MPD value while the person crossing behind has a negative MPD value. This means that whenever roles are changed the sign of SMPD at the start of the interaction will be different from the sign at the end.

Using this modified measure, it was found that people preferred to cross behind when avoiding collision with a robot that is in forward motion but not reacting to other obstacles [START_REF] Vassallo | How do walkers avoid a mobile robot crossing their way?[END_REF]. This behavior was associated with perceived safety as the person crossing behind can see the person crossing in front in their field of view until the end of the interaction. Change on crossing order can be perceived as a problematic behavior given that it was found to increase the time required to avoid collision [START_REF] Vassallo | How do walkers behave when crossing the way of a mobile robot that replicates human interaction rules?[END_REF].

Conversely, in a subsequent work [START_REF] Vassallo | How do walkers behave when crossing the way of a mobile robot that replicates human interaction rules?[END_REF], whenever people perceived the robot as moving and avoiding collision in a human-like fashion they were more likely to preserve the currently perceived crossing order and behave in a similar way as if there were two people (such as in the experiments of [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF]).

Homotopy class decision

Although the concept of crossing order is used extensively in the literature [START_REF] Vassallo | How do walkers behave when crossing the way of a mobile robot that replicates human interaction rules?[END_REF][START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF], it is not general enough to describe all collision avoidance situations. As an example, in future head-on collision scenarios crossing order is undefined. More generally, in any collision scenario where the derivative of the bearing angle is exactly equal to zero crossing order cannot be determined and it is either ambiguous or undefined at that point in time.

Given the cases where crossing order is unable to characterize collision avoidance, a more general way to describe the manner in which people avoided the collision is necessary. To this end, the concept of homotopy class can be used. This concept was defined in [START_REF] Kuderer | Teaching mobile robots to cooperatively navigate in populated environments[END_REF] as the side in which agents pass each other. As can be seen in Fig. 234, trajectories within the same homotopy class can be continuously deformed into each other.

In [START_REF] Bhattacharya | Search-based path planning with homotopy class constraints[END_REF], it was shown that two trajectories are homotopic if and only if both have the same integral of their derivative of the bearing angle. Each discrete decision about whether to pass left or right of someone represents a homotopy class decision. In [START_REF] Kuderer | Teaching mobile robots to cooperatively navigate in populated environments[END_REF], the homotopy class of each distinct trajectory pair was calculated using

Θ p r = t αr,p (t)dt (2.3)
In this formulation, agents that pass each other on their right side will generate a Θ p r = π while passing each other on the left side results in Θ p r = -π. This formulation is elegant as its value is independent of the duration of collision avoidance. However, it is important to note that although Θ p r correctly associates the choice of homotopy class of two actual (or predicted) trajectories, to complement these results [START_REF] Kuderer | Teaching mobile robots to cooperatively navigate in populated environments[END_REF] also built a probability distribution that is able to predict the most likely choice of homotopy class for any given person in the environment.

The relation between number of obstacles and possible combinations of homotopy class decisions is exponential. Choosing the most likely discrete decision on whether to cross on the right or left side of a person is insufficient to accommodate scenarios of uncertainty. In the absolute worst case of future collision, that happens in symmetric collision scenarios, people cannot predict the order in which they will reach their intersection point (see Sec. 2.2.1). In more general terms, people find it more difficult to determine the correct homotopy class when they approach each other in near symmetric scenarios. Thus in a perfectly symmetric scenario, in the absence of other obstacles, two people involved in collision avoidance would choose to cross in front or behind with equal probability.

Discussion

In this section we discussed several factors that allowed one to characterize collision avoidance progress. Our first step is establishing the focus of our work on using only situational factors. In that sense, personal factors such as age, gender, emotional state and physical properties of one's body (e.g. body size and weight) were not considered. Although we established through careful analysis of the literature that personal factors can impact collision avoidance behavior and group organization, in [START_REF] Knorr | Influence of personand situation-specific characteristics on collision avoidance behavior in human locomotion[END_REF] it was shown that situational factors represent the most relevant factors in determining collision avoidance behavior.

Our work is based on using situational factors to describe current and future behavior of people. The robot would then attempt to replicate this decision in order to achieve more human-like behavior. In other words, predict the manner in which situational factors determine the role and the mean effort required to avoid a future collision. Particularly in cases where there is a non-trivial motion adaptation required for collision avoidance.

Another objective of our work, that also relies on some of the aforementioned situational factors, intends to evaluate and mitigate the potential negative impact of role reversals on collision avoidance. More specifically, our contribution lies in using situational factors to determine when the homotopy class decision is ambiguous e.g. derivative of the bearing angle is zero. In such cases, both agents may incorrectly choose the same role for collision avoidance, thus their motion adaptations, when seem in conjunction, would be detrimental to collision avoidance.

Chapter 3

Robot motion among people As more robots share living spaces with people, work in Human Robot Motion (HRM) has seen an increased interest in recent years. Works in the domain of HRM attempt to model the manner in which robots should move among people.

Moving in an unnatural or unsafe manner can cause discomfort for people around the robot. As there is currently no commonly agreed formal definition for comfort or discomfort within the domains of HRM or robotics. In our work we rely on a qualitative definition for comfort, proposed by [START_REF] Kolcaba | Holistic comfort: operationalizing the construct as a nurse-sensitive outcome[END_REF], as "the state in which the body is relieved of unpleasant sensory or environmental stimuli". Even though alternate terms also exist, such as hindrance in [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], disturbance in [START_REF] Cosgun | Anticipatory robot path planning in human environments[END_REF] and social work in [START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF], we aggregate these similar terms within the more general concept of comfort. Given this context, a robot that moves in what we call an acceptable or appropriate manner minimizes the amount of discomfort caused to a person or to a group due to the robot's motion (or lack thereof). For instance, a robot that acts in a human-like manner was found to reduce global cognitive effort for people in the environment in [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF] and by consequence reducing discomfort caused by the robot's presence.

The concept of comfort can also be used for vehicles. In [START_REF] Gulati | High performance control for graceful motion of an intelligent wheelchair[END_REF] defines a comfortable wheelchair ride as a ride having low jerk, smooth velocity and acceleration without oscillation that maintains sufficient clearance from its surroundings. The model shows that people prefer to navigate at 1 4 distance of a corridor wall in order to use one half of the corridor and leave the other half free. Such situation, however, is not the main focus of our work.

In this chapter, we first introduce several different areas of study within HRM. For each area we present the most important works and their contributions to the state of the art. Finally, we discuss where our work fits within HRM and how our contributions improve upon its state of the art.

Accounting for social spaces during navigation

People consider some regions as belonging to them, as showcased in Fig. 3-1, thus whenever another agent enters this region discomfort can be caused to the affected person. The size and shape of these regions, called social spaces, depends on several factors such as current velocity and activity.

Personal space

One of the core concepts in human interaction in social spaces is called proxemics. It can be defined as a natural distance people put between themselves in different social situations [START_REF] Rios-Martinez | From proxemics theory to socially-aware navigation: A survey[END_REF]. The term was coined in [START_REF] Hall | The Hidden Dimension[END_REF], where different social situations were described and the resulting differences in a person's social space compared.

The social space of an individual has a different shape than that of a group (sometimes referred to as "we-space"). According to [START_REF] Hall | The Hidden Dimension[END_REF], an individual social space can be broadly categorized in four different concentric circles, these are: The public zone is not seen as belonging to the person, in this sense, people you are not familiar, nor interacting with, can cross it without causing discomfort. In contrast, the Social Zone is commonly reserved for acquaintances. Friends and family are able to enter the personal zone, while in general the Intimate Zone is reserved for whispering, embracing and similar actions. This proxemics model has been used throughout several HRI concepts to develop better social robot behavior during interaction with an individual or a group.

Several studies detected changes in the shape and size of the zones in different situations. In [START_REF] Hayduk | The shape of personal space: An experimental investigation[END_REF], it was found that people are more protective of their frontal space than their back. Furthermore, in Gerin-Lajoie et al. ( 2008) asymmetries in the personal space were found, being larger in the opposite side of the person's dominant hand.

A long-term study on proxemics between human and robot found that a distance comfortable for people between a person and a robot remains stable after short adaptation period [START_REF] Walters | A long-term human-robot proxemic study[END_REF]. Moreover, people allowed for less distance when they are approaching a robot than when a robot approached them.

In an attempt to map the best manner for a robot to approach a person, while respecting their personal space, [START_REF] Torta | Design of robust robotic proxemic behaviour[END_REF] designed a navigation approach that respects personal space and chooses the best direction to approach a person. To that end, an user study involving a bipedal robot approaching people was made and their preferences were evaluated.

Other factors can also affect the size of a personal space. For instance, whenever the gaze direction of the robot was oriented towards a person's face, the minimum comfortable distance increases for women and decreases for men [START_REF] Takayama | Influences on proxemic behaviors in human-robot interaction[END_REF]. Another important factor was that in corridors people perceived negatively a robot that passes within the intimate space of a person but also a robot that excessively increases its lateral distance to the person [START_REF] Pacchierotti | Evaluation of passing distance for social robots[END_REF]. The interaction space has to be accounted for during motion planning. Appropriate motion represents more than just guaranteed safe motion. Trajectory in red is safe but not appropriate while trajectory in green is both safe and appropriate.

Activity, interaction and affordance spaces

Beyond the aforementioned personal space, there are three important spaces that have an important social significance: interaction, activity space and affordance space.

A social space that is formed through an action that is being performed by people within a certain space is called an activity space [START_REF] Lindner | Towards a formalization of social spaces for socially aware robots[END_REF]. In that sense, a robot passing through a soccer field while a match is happening, even if in a collision free manner, would not be an acceptable motion because it violates an existing activity space.

An important subtype of activity space is formed when two or more people are involved in an interaction. This behavior engenders what is called an interaction space [START_REF] Lindner | Towards a formalization of social spaces for socially aware robots[END_REF]. Thus a robot should not violate the space defined by this interaction, moreover, it should account for what is defined as the buffer region [START_REF] Kendon | Conducting interaction: Patterns of behavior in focused encounters[END_REF] around an interaction space that also should not be invaded upon. In Fig. 3-2, the agents considers two possible plans, one collision free but not an appropriate motion while the other is both collision free and appropriate.

A motion planner capable of accounting for both personal and interaction spaces was developed in [START_REF] Rios-Martinez | Intention driven human aware navigation for assisted mobility[END_REF]. This planner built a social filter composed of two modules 1. a personal space module that creates a costmap map composed of two gaussians centered at the front and at the back of each person. As they found that people are more sensitive to the frontal area, the front Gaussian is larger;

2. and also an interaction space module that associated an additional cost to candidate trajectories whenever a trajectory would pass within the space formed by two people interacting.

These social modules were integrated into the into their approach, called "RiskRRT" to allow a robot to navigate with socially-aware behavior.

Another approach that is able to account for interaction spaces was presented in [START_REF] Cosgun | Anticipatory robot path planning in human environments[END_REF]. In their approach, path length cost, safety and the discomfort caused by disturbing an interaction space are accounted for. The disturbance in interaction space is calculated by first checking whether the robot path intersects a line segment between all pairs of people. Based on this, the actual cost of intersecting this line is determined based on the current orientation of each pair of people, a pair facing each other would incur higher trajectory costs while a pair of people facing opposite directions would incur zero additional cost.

Although interaction and personal spaces have been explored consistently in the aforementioned works, other spaces have received moderate attention. Among these we highlight the affordance space, which have been defined in [START_REF] Gibson | The ecological approach to visual perception: classic edition[END_REF] as dispositional properties of an environment in which actions can be performed. A soccer field or a telephone that are not being used are not activity spaces but represent instead affordance spaces. As such, an activity space requires actions by one or more people within its space to exist while affordance spaces represent a potential for activity.

Building upon this concept, in [START_REF] Lindner | Affordance-based activity placement in human-robot shared environments[END_REF], a model was developed that is able to reason about whether an agent should use an affordance space or not. This is done while taking into account the possible actions of other agents and also the available affordance spaces. These two data points are used to build an affordance-space map that is used to reason about the impact of the robot's decisions on other agents. In that sense, an agent would be able to balance the urgency of an activity to the discomfort it could cause to people (blocking a door for example).

Approximating internal state of a person

While respecting social spaces is an important component of appropriate motion, understanding the perception of people regarding the robot's intention is also of fundamental importance.

For example, for maximum comfort should a robot approach a person from the side or directly from the front? Several works attempted to answer related questions using the concepts of visibility, legibility and perceived safety.

3.2.1

The impact on comfort of the presence of a robot [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF] has shown that in the presence of a robot, people feel more comfortable when the robot is within their field of view. To that end, their path planner created a costmap around each person where higher costs are given to regions further away from the center of their field of view. Thus, a robot would avoid going behind a person unless the path in front of the person's field of view was significantly longer. Furthermore, another costmap was created to account for hidden zones, where they account for the fact that when a robot is passing behind an obstacle the person would not feel threatened by the motion of the robot. However, to avoid a potential surprise factor, as when a robot suddenly appears from behind an object, an extra cost is added behind obstacles to allow for larger distance between the robot and obstacles that occlude the robot from a person's view. This larger distance causes, in turn, a smoother entrance into a person's field of view.

Although [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF] assumes that maintaining the robot within the visual field is desirable, other researchers have shown that having the robot in view can be distracting. Based on a similar premise, a model was devised in [START_REF] Maisonnasse | Attentional model for perceiving social context in intelligent environments[END_REF] to approximate direction of a person's attention in a given situation. To that end, they build a model inspired in the physical concept of gravity, in this model they calculate an attraction vector that encodes the average attention gaze direction and intensity. This attraction vector changes in tandem to the position and velocity of other nearby agents. This vector is then combined with the current velocity of the person to find an attention vector.

In order to improve upon such concept of attention, in [START_REF] Paulin | Using human attention to address human-robot motion[END_REF], a model was created in which the robot evaluates multiple possible attention vectors -an attention mapof a person within the environment. The attention map is calculated using a custom visual saliency method inspired on the human visual system. The potential distraction caused by a robot may be evaluated with respect to multiple places observed by the person. Both [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF] and [START_REF] Paulin | Using human attention to address human-robot motion[END_REF] also include a surprise factor but in the latter it is determined from the rate of change of the attention map resulting from the robot's motion. Finally, in order to find acceptable paths based on these premises, multi-criteria optimization based on Approximation-Guided Evolution (AGE), described in [START_REF] Wagner | Efficient optimization of many objectives by approximation-guided evolution[END_REF], was chosen given its ability to accommodate multiple optimization objectives.

Legible motion during navigation among people

Legible navigation can be described as a robot motion that allows a person to intuitively understand the robot's intentions while navigating [START_REF] Kruse | Legible robot navigation in the proximity of moving humans[END_REF] such as shown in Fig. 3-3. Other terms in the robotics literature that convey similar meanings are: readability, predictability and anticipation [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF].

Legible motions should indicate its goal direction and also demonstrate its awareness of both static and dynamic obstacles [START_REF] Lichtenthaler | Influence of legibility on perceived safety in a virtual human-robot path crossing task[END_REF]. For example, in Fig. 3-3a, the person is unable to perceive the goal of the robot and is thus forced to avoid potential collision. On the other hand, in Fig. 3-3b, the robot clearly indicates early on its intention to turn which allows the person to avoid unnecessary motions. The concept of legibility is also associated with the concept of field of view (described in Sec. 3.2.1). For a motion to be legible the person should be able to actually see the robot, thus motion planning should attempt to prefer maintaining the robot within a person's field of view whenever feasible. This means not approaching a person directly from the back.

In [START_REF] Lichtenthaler | Influence of legibility on perceived safety in a virtual human-robot path crossing task[END_REF], it was suggested that a person would perceive a situation as more comfortable if she can predict the next actions of the robot. A more precise definition of legible motion was given in [START_REF] Kruse | Exploiting human cooperation in humancentered robot navigation[END_REF] as: "A prerequisite of human comfort is legible behavior, which means that an ordinary, uninstructed person can understand and anticipate the robot's actions."

Based on this definition, [START_REF] Kruse | Exploiting human cooperation in humancentered robot navigation[END_REF] designed a navigation strategy that allows a robot to convey its intention to move through a space that a person currently occupies. Their conclusion is that a robot can exploit the fact that people are benevolent and capable of self-propelled motion in order communicate through motion the robot's intention of passing through a region that a person currently occupies.

The benefits of readable motion were extensively studied in [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF], where, in a mutual avoidance experience, readable motion reduced planning effort for people in the environment. Their work also showed that people utilize similar motion planning behaviors in the vicinity of robots.

Human-aware collision avoidance

To accommodate the presence of dynamic obstacles, trajectory deformation ap-proaches, such as in [START_REF] Delsart | Navigating dynamic environments using trajectory deformation[END_REF], add the time dimension in the information regarding an obstacle future behavior. This makes it possible to deform the space-time curve in response to dynamic obstacles as well as other constraints such as feasibility and connectivity. This approach, however, does not account for the collaborative nature of human behavior and instead treats people as moving obstacles.

Treating people as moving obstacles, a non-HRM approach, in sufficiently complex scenarios, would cause the "freezing robot" [START_REF] Trautman | Unfreezing the robot: Navigation in dense, interacting crowds[END_REF]. This situation arises when the robot motion planner eventually decides that all forward paths are unsafe and the robot either halts or engages in convoluted avoidance maneuvers.

People however are benevolent agents capable of self-propelled motion. In the context of HRM people can be treated as potentially cooperative agents when involved in tasks that have shared goals with a robot. In Fig. 34, we present a hypothetical situation in which a robot treats a person as just a moving obstacle and another situation where the person proactively contributes to collision avoidance.

In this section we explore two main directions in which HRM can account for people during motion planning as more than moving obstacles during collision avoidance. The first approach balances, during robot motion planning, the amount of contributions for the robot to avoid collision with respect to contributions of other people in the environment. In the second approach, people's behaviors are learned or inferred from data and replicated.

Accounting for the reaction of people to a robot motion

Encoding the usual reaction of a person to a given robot motion allows one to minimize discomfort for people during collision avoidance. To that effect, many human-like models have been utilized to allow a robot to replicate or at least account for a person's behavior.

In [START_REF] Cosgun | Anticipatory robot path planning in human environments[END_REF], a robot is able to predict how standing people that are inadvertently blocking its way will react to its motion, that is, in which manner they will allow the robot to pass and how much discomfort this would cause. This allows a robot to pass through regions that would have been hard or impossible otherwise. This is done through the use of the Social Force Model (SFM), presented in [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF], to calculate people's reaction (as a group or individual) to a particular robot plan.

For situations where people are already in motion, in [START_REF] Shiomi | Towards a socially acceptable collision avoidance for a mobile robot navigating among pedestrians using a pedestrian model[END_REF] a robot navigated inside a shopping mall using an approach based on Social Force Model with explicit Collision Prediction (SFM-CP), a version of SFM tuned with empirical data from human motion [START_REF] Zanlungo | Social force model with explicit collision prediction[END_REF]. The main contributions of [START_REF] Shiomi | Towards a socially acceptable collision avoidance for a mobile robot navigating among pedestrians using a pedestrian model[END_REF] were two experiments to evaluate their SFM-CP based robot control approach. In the first experiment, people were put in a future head-on collision scenario with a robot in order to qualitatively assess a person's comfort during the interaction in relation to another standard approach in the literature. In their second experiment, a robot, also using their approach based on SFM-CP, navigated in a shopping mall and its trajectory and distance to other people where judged by two people with regards to safety. Finally, they found their approach avoided unsafe situations better than other navigation methods such as Dynamic Window approach [START_REF] Seder | Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[END_REF].

To better quantify the amount of change in a person's motion caused by the robot, in Ferrer and Sanfeliu (2014b) a discomfort-like measure was used as an additional cost for each candidate trajectory to the robot's goal. The discomfort is based on the potential reaction of a person to a given robot trajectory and its cost was calculated using the Extended Social Force Model (ESFM) which is described in Ferrer et al. (2013b). Given this potential reaction from each person near the robot, their discomfort-like measure was associated to each potential candidate trajectory during trajectory planning. Such formulation allows one to give precedence to trajectories that have smaller impact on the motion plan of nearby people.

Robot-person collaboration with joint trajectories

Instead of planning a robot motion that attempts to minimize the overall impact in a person's predicted motion, many approaches instead attempt to replicate joint behavior between people when avoiding collision with each other.

During collision avoidance each person does not necessarily attempt to solve the collision avoidance problem by themselves. Each person in the environment account for what is called joint collision avoidance [START_REF] Trautman | Unfreezing the robot: Navigation in dense, interacting crowds[END_REF]. In order to explicitly replicate such human behavior, [START_REF] Kuderer | Teaching mobile robots to cooperatively navigate in populated environments[END_REF] tele-operates a robot in the presence of humans in order to learn a model of its own navigation behavior and also the behavior of pedestrians and of their cooperative interactions.

A similar approach was done in [START_REF] Kretzschmar | Learning to predict trajectories of cooperatively navigating agents[END_REF], where a number of features such as time, acceleration, velocity and distance are used to learn probability distribution of possible joint trajectories between people during collision avoidance. In practice, to find actual joint trajectories for a given situation, a gradient based optimization named Resilient Propagation (RPROP) (see [START_REF] Riedmiller | A direct adaptive method for faster backpropagation learning: The rprop algorithm[END_REF]) was used. In Kretzschmar et al. (2016b), an extended version of their work also explicitly accounted for: distance to static obstacles, group behavior and clearance to other agents.

Following flow of people to avoid collision situations

The approaches detailed in Sec. 3.3.1 and 3.3.2 and attempt to avoid immediate collisions while also accounting for reaction of people to a given motion plan. Although this may efficiently avoid a immediate collision situation, a human motion planner should also move in a way that causes future collision situations to be less likely to occur. [START_REF] Henry | Learning to navigate through crowded environments[END_REF] describe an approach where the robot is allowed to follow groups of people that are going into a similar direction as the desired direction of the robot, thus avoiding collisions. The behavior of nearby groups of people were represented using their density and velocity. Based on this representation, an inverse reinforcement learning approach [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF] was used to learn cost weights for observable positions based on density and velocity of people in that area with respect to the robot's goal direction. Finally, to calculate the trajectory that best respects the flow of people an A search [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF]) was used on the weighted map.

In a similar direction, in [START_REF] Kim | Socially adaptive path planning in human environments using inverse reinforcement learning[END_REF], an inverse reinforcement learning approach was used to effectively follow the flow of people. In their use case, an autonomous wheelchair navigation strategy was develop by extracting features from a virtual grid in front of the robot, for each position in the grid the extracted features were: density, speed, direction and distance from the cell to the goal. These features were then used to learn using inverse reinforcement the weights for a cost function that best represent the behavior seen during demonstration from people.

Discussion

The breadth of subjects that were already explored within the state-of-the-art of HRM is significant. Among these subjects, our work falls within the scope of human-aware collision avoidance, where our major contribution lies in examining the problem in terms of distribution of motion adaptations between agents during collision avoidance.

In [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF], it was shown that people mutually solved the collision avoidance task but their contribution is not symmetric. In particular, in an orthogonal crossing situation, a person who will arrive second at the crossing contributes more than the other to avoid the collision in terms of motion adaptation. Therefore, attempting to use human-like models such as SFM, ESFM and SFM-CP to minimize the impact of the candidate robot motion in a person may lead to a robot behavior that is not human-like. Similarly, our intention is also not to directly encode joint trajectories using features such as position and distance between agents. Instead our works captures the expected collaboration in terms of distribution of motion adaptations between agents. Our hypothesis is that a robot that respects what we call "effort distribution" would behave in a human-like manner during collision avoidance.

Although this chapter provided an overview of where our approach lies within the domain of HRM, a more in-depth comparison of our approach with respect to related works is still necessary. In Chapter 4, we present several methods dealing with collaborative collision avoidance while detailing their advantages and limitations. This chapter surveys existing approaches that deal with the problem of collaboration between agents during collision avoidance. Although some of these works are not necessarily applied in the domain of Human Robot Motion (HRM), several concepts, common among these works, can serve as a baseline for comparison with our contributions.

Chapter 4 Collaboration during collision avoidance

Collaboration during collision avoidance is defined in this work in terms of complementary motion adaptations with the shared purpose of avoiding future collision between agents. Given this definition, approaches that tackle such problem must define the manner in which this collaboration takes places. Moreover, in order to better highlight their collaboration strategy, whenever feasible, their collision avoidance models and the assumptions made in their collaboration strategy are presented in greater detail.

Collision avoidance collaboration in reactive agents

Reactive approaches can provide a simple solution for collision avoidance behavior. With such approaches, an agent takes collision avoidance decisions based on the current state of both agent and obstacles (moving or static). In this section we review work on reactive approaches with a focus on their collaboration strategy during collision avoidance.

Synthetic vision navigation

Bottom-up approaches for human-like navigation are based on a set of basic properties that generate complex agent behavior. In this context, synthetic vision approaches attempt to simulate key concepts related to vision of people in order to engender realistic navigation behavior. Several approaches simulate key concepts related to perception of obstacles by people in order to avoid collisions. For instance, in [START_REF] Kuffner | Fast synthetic vision, memory, and learning models for virtual humans[END_REF] an agent simulates the visual perception of a person in order to navigate in the environment with multiple obstacles. Another approach, presented in [START_REF] Dutra | Gradient-based steering for vision-based crowd simulation algorithms[END_REF], used a cost function to evaluate the situation of an agent with respect to their target and also its risk of collision. Their method is able to not only avoid collision situations but also minimize the chances of future collision.

In [START_REF] Ondrej | A synthetic-vision based steering approach for crowd simulation[END_REF], such concept of synthetic vision was used to replicate the manner in which people use their visual system within a crowd. Using their approach for navigation, simulated people were able to move in crowds while avoiding collision with an unbounded number of other agents while using just three variables to describe each other agent. This was motivated by a previous study showing that these variables were sufficient to explain much of the collision avoidance decisions of a person, these variables are the bearing angle and its derivative and time to interaction [START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF].

Given this background, let α i , αi , tti i denote, respectively, the bearing angle, the derivative of the bearing angle and the time to interaction of one agent with respect to another agent i. In [START_REF] Ondrej | A synthetic-vision based steering approach for crowd simulation[END_REF], an agent determines a collision risk with another agent i using

τ 1 (ttc) =    τ 1-(tti) = a -b • tti -c if αi < 0 , τ 1+ (tti) = a + b • tti -c otherwise . (4.1)
where the parameters a = 0, b = 0.6 and c = 1.5 where manually defined based on their experimental data. Using this formulation, an agent perceived a risk of collision with p i whenever tti i > 0 and αi < τ 1 (tti i ). In practice, this means that a αi ≈ 0 causes collision avoidance to happen even if time to interaction is above eight seconds. Conversely, a sufficiently high value of | αi | would cause collision avoidance only in case time to collision is near to zero. Given sufficient risk of collision, their collision avoidance motion for p i depends on the values of tti i and αi . The heading change can be calculated 1 as

∆ θ =    αi -τ 1+ (tti i ) if αi < 0 , αi + τ 1-(tti i ) otherwise . (4.2)
where ∆ θ denotes the necessary change in the current heading. Based on this equation, the role of an agent during collision avoidance is strictly based on the sign of αi . Moreover, for the case with two agents, the change in heading depends on tti i and αi which are the same for both the agent crossing in front and the agent crossing behind. This means that, in absence of other obstacles or angular constraints, the heading adaptations done by the agents are of equal amount. A similar logic can be used for speed adaptations.

Velocity obstacles and related methods

The concept of Velocity Obstacles (VO) was introduced in Fiorini and Shiller (1998). The VO represent a set of velocities from one agent that would result in collision with an obstacle moving at a certain velocity.

A natural extension of the VO method for a case with two autonomous agents was done in [START_REF] Van Den Berg | Reciprocal velocity obstacles for real-time multi-agent navigation[END_REF] and named Reciprocal Velocity Obstacles (RVO). This method can avoid collision as long as both agents chose velocities outside the RVO induced by the other agent. However, it was found that under certain conditions RVO could not guarantee collision avoidance (van den Berg et al., 2011). To overcome this limitation the concept of Optimal Reciprocal Collision Avoidance (ORCA), also called RVO 2, was introduced in van den Berg et al. (2011).

To avoid a collision both ORCA and RVO follow a similar principle, they calculate the change in relative velocity between two agents that avoids a collision and distribute this change in velocity among them. More specifically, consider a situation where two agents q and p, with desired velocities v des q and v des p need to avoid a collision with each other. In this case, RVO finds the smallest change in the relative velocity ( v des q -v des p ) that avoids a collision between them (van den Berg et al., 2011), this is given by u as

u = ( arg min v∈∂ VO τ q|p ‖ v -( v des q -v des p )‖) -( v des q -v des p ) (4.3)
where ∂ VO τ q|p is the set of changes in relative velocity that are in the threshold between collision and no collision -the minimum change in relative velocity that avoids a collision. The change in relative velocity is divided equally between the two agents (van den Berg et al., 2011), that is, each agent will change its velocity by 1 2 u. A recent work has shown a non-trivial change in collision avoidance behavior of agents when using non-equal distribution of the change in relative velocity between agents [START_REF] Rakotoarivelo | Heterogeneous pedestrians behaviors through asymmetrical interaction[END_REF]. Although interesting changes in collision avoidance behavior were shown, no particular strategy to choose a particular distribution of change in relative velocity was presented.

Finally, in ORCA and RVO the crossing order decision is based on a similar concept as the derivative of bearing angle. However, in case of ambiguity the algorithm will bias the decision towards a particular side. In other words, in case the derivative of the bearing angle between two agents is zero the algorithm establishes a convention so that agents always choose different crossing orders.

Social Force Model and related methods

The concept of social forces can be summarized as representing internal motivations of pedestrians through the use of attractive and repulsive forces to elements in the environment [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF]. In the Social Force Model (SFM), introduced in Helbing and Molnár (1995), the forces that affect a given agent can be partitioned in four distinct categories:

1. a force attracting the agent towards his goal; 2. a repulsive force to keep agents away from static obstacles and walls; 3. another force to attract an agent to certain people e.g. friends;

4. finally, a repulsive force that attempts to maintain distance to other pedestrians.

Our interest lies on the force that attempts to maintain a certain distance to pedestrians which also encodes collision avoidance behavior. Based on this force, the movement of an agent is realized by following the negative gradient of the combination of attractive and repulsive potentials.

Even though SFM has been extensively used to simulate crowds, in [START_REF] Steffen | A modification of the social force model by foresight[END_REF], it was empirically demonstrated that distance-based repulsive forces are incapable of describing individual pedestrian behavior. For instance, during simulated experiments with SFM in single lane head-on collision scenarios between two people, SFM was unable to modulate an agent's speed to avoid collision without oscillations in speed. Although adding foresight to agents in this scenario alleviated the oscillations in some scenarios, more complicated situations once again caused unrealistic oscillations in speed and heading.

Although newer approaches have been developed to tackle the aforementioned issue, such as [START_REF] Moussaïd | Experimental study of the behavioural mechanisms underlying self-organization in human crowds[END_REF], [START_REF] Zanlungo | Social force model with explicit collision prediction[END_REF]Ferrer et al. (2013b), recent works have found that the SFM still has shortcomings when dealing with pedestrians in low-density scenarios (Kretzschmar et al., 2016b).

Planning trajectories for collaborative collision avoidance

Instead of reasoning in a reactive manner about the motion of nearby people, one can plan over whole trajectories. Planning whole trajectories can allow one to produce plans that are based on the current and future state of agents and obstacles.

Learning joint trajectories between agents

In order to predict future interaction with pedestrians and also to allow navigation that is comfortable for them, [START_REF] Kuderer | Feature-based prediction of trajectories for socially compliant navigation[END_REF] proposed to learn, from experiments between people in collision avoidance situations, the cooperative collision avoidance behavior between agents using a probability distribution over joint trajectories.

The concept of joint trajectories can be summarized in two steps. First a trajectory j p from an agent p is defined as a continuous function t ↦ → j p (t) ∈ 𝒥 (4.4) where this function maps every time t to a configuration j ∈ 𝒥 . Secondly, the joint trajectory q, represented as the Cartesian product of the trajectories of N agents, is then defined as:

q(t) = j 1 (t) × • • • × j N (t) ∈ 𝒥 N (4.5)
In [START_REF] Kuderer | Feature-based prediction of trajectories for socially compliant navigation[END_REF], the space of joint trajectories 𝒥 N is partitioned into all correct combinations homotopy class decisions2 for N agents. For instance, considering two agents there would be two partitions of 𝒥 N . These two partitions represent agents crossing each other on the right side or in the left side.

Based on this concept, in [START_REF] Kuderer | Feature-based prediction of trajectories for socially compliant navigation[END_REF] the behavior of agents over each correct combination of homotopy class decision was reproduced using features to encode a prob-ability distribution over joint trajectories, this behavior was learned through experiments with people in collision avoidance situations. Each unique combination of homotopy class decisions between agents is associated with a probability of occurrence. This means that a robot could always choose the most probable homotopy class decisions when planning its collision avoidance motion.

Several works proposed improvements to this approach. For example, in order to account for the fact that people can react differently to robots, in [START_REF] Kuderer | Teaching mobile robots to cooperatively navigate in populated environments[END_REF], instead of learning from experiments with people, a tele-operated robot was used to learn the probability distributions over joint trajectories. Another improvement, proposed in Kretzschmar et al. (2016a), encoded feature expectations using Hybrid Monte Carlo [START_REF] Duane | Hybrid monte carlo[END_REF] sampling in order to reduce the impact from samples of improbable homotopy classes.

Although their approach and the aforementioned improvements were shown to reproduce trajectories generated by their experimental data, they did not mitigate the negative impact of situations in which the probability for two different combinations of homotopy class decisions were similar. This would mean that people and robot could attempt to solve future collision by incorrectly choosing the same crossing order -a decision detrimental to collision avoidance.

Kinodynamic planning of trajectories

The term kinodynamic was defined in LaValle and Kuffner Jr (2001) as a "feasible openloop trajectory that satisfies both global obstacle constraints and local differential constraints". This concept was applied in [START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF] to allow a robot to plan feasible trajectories towards a goal that also account for the potential reaction it causes from a person.

Given that the robot plans over whole trajectories, it is necessary to estimate the goal and motion of people. To that end, a combination of approaches were integrated into the kinodynamic planner [START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF]. For instance, the goal of nearby people was calculated based on a Bayesian approach described in Ferrer and Sanfeliu (2014c). Moreover a module based on SFM and presented in Ferrer and Sanfeliu (2014a) was used to estimate the next state of a person given a robot action.

Given the robot action and the impact it causes in a person over multiple time steps, a measure called social work, that was presented in Ferrer et al. (2013a), was used to calculate the impact of the robot trajectory in a person's motion. This measure was defined as

W r (t, ζ ) = W r (t, ζ ) + ∑ p∈P W p,r (t, 0) (4.6)
where ζ represents learned weights of the system, W r (t, ζ ) is the total work done by the robot while W p,r (t, ζ ) represents the work done by a person p ∈ P given the the chosen motion for the robot.

Based on this measure, their approach then attempts to minimize the work done by both the robot and the person when planning a partial trajectory towards the robot's goal Regardless of the previously discussed shortcomings in reproducing the reaction of people in low density scenarios using SFM in Sec. 4.1.3, our assumption is that minimizing discomfort-like measures without accounting for people expectations can generate motions that are not human-like. In that sense, in our approach collision avoidance motions respect the expected distribution of motion adaptations instead of attempting to minimize a cost such as the social work.

Discussion

In this section we reviewed works that share a common challenge: collaboration between agents during collision avoidance. These approaches have directly or indirectly accounted for other agents as more than moving obstacles.

Among these reviewed approaches, as shown in Table 4.1, only one other human-like approach attempted to replicate the manner in which people mutually share motion adaptations to avoid collision. In most approaches, in the absence of other obstacles, the amount of motion adaptations between two agents to avoid collision is similar. The exception is [START_REF] Kuderer | Feature-based prediction of trajectories for socially compliant navigation[END_REF], where this asymmetric behavior can be encoded within their probability distribution over joint trajectories given sufficient data.

In the context of collaborative collision avoidance, to our knowledge, our approach is the first one that explicitly accounts for (near) symmetry scenarios in which there is a non-trivial chance of person and robot choosing the same crossing order (opposite homotopy class decisions). To tackle this problem, our collision avoidance approach mitigates the chance of remaining in an ambiguous situation in the next decision step in case both agents choose the same crossing order. Even though in [START_REF] Kuderer | Feature-based prediction of trajectories for socially compliant navigation[END_REF] the probability of each combination of homotopy class decisions occurring is calculated, their approach only accounts for correct homotopy class combinations i.e. agents are always assumed to correctly choose the same homotopy class.

In chapters 5 and 6 our solution to the aforementioned limitations of current approaches are presented in details. This chapter describes our model for the way people collaborate to avoid a possible collision. Our focus is on dyadic collision avoidance where both agents are involved in goal directed locomotion. In this sense, we do not account for other human tasks during locomotion, such as: wandering [START_REF] Lai | Wandering behaviour in people with dementia[END_REF] and following other people [START_REF] Hay | Following their companions as a form of exploration for human infants[END_REF].

Approach

Earlier work on this subject was presented in publications: Silva and Fraichard (2017) and [START_REF] Silva | Human inspired effort distribution during collision avoidance in human-robot motion[END_REF]; this chapter presents only the most recent version or our approach, as described in [START_REF] Silva | Human inspired effort distribution during collision avoidance in human-robot motion[END_REF]. This most recent version of our model is a strict improvement over our previous work, which is shown as originally published in Annex I.

Overview of the problem

A robot that is attempting to avoid potential collisions with people needs to account for their expectations when planning its avoidance motion. As discussed in Sec. 2.2.1, the initial conditions before collision avoidance usually allow people to determine whether there is a collision risk and and when required, how to avoid such collision.

Depending on situational factors that are usually able to describe a given collision situation, the distribution of motion adaptations between the person crossing in front and the person crossing behind (see Sec. 2.2) will not be necessarily equal. This was confirmed in [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF], where dyadic collision avoidance experiments observed that the reactions to avoid collision are not symmetric and depend on crossing order. More specifically, the person crossing behind, as an overall, was responsible for around 60% of the motion adaptations to avoid collision while the person crossing in front was responsible for 40%. Their experiments assumed orthogonal collision avoidance scenarios, that is, crossing angles near 90°.

Our work intends to improve upon the results above in two main ways. Our first objective is to generalize the conclusions to other crossing angles and also to predict, given a set of situational factors as input, the approximate distribution of effort for each particular situation (instead of on the average). Approximating effort distribution for each particular situation would allow one to replicate expectations of people during collision avoidance. As a consequence, this would potentially reduce the cognitive effort for people in the environment as people could act as they would with another person [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF].

Our initial implementation of this model, presented in [START_REF] Silva | Human robot motion: A shared effort approach[END_REF], attempted to directly use the grand average value obtained in [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF] to distribute effort. However, several situations were not properly accounted for with our original approach, specifically:

1. Our collision avoidance approach, presented in [START_REF] Silva | Human robot motion: A shared effort approach[END_REF], was based on a study focused on situations with 90°crossing angle. Generalizing these conclusions for additional crossing angles could result in a difference in behaviour.

2. People coming from the edge of the field of view may be less responsible for collision avoidance than otherwise. This can be a consequence of many factors, such as visibility concerns or even the shape of one's personal space.

3. The impact of situational factors such as speed and time to collision could affect the distribution of motion adaptations. For instance, smaller time to collision can be perceived as having a higher collision risk for a given role.

Thus, an approach to model distribution of motion adaptations between people should satisfactorily solve this limitation and provide more natural collision avoidance motions in relation to our previous approach. To that end, a dataset of human behavior during collision avoidance was used in our work and is described in the following section.

Dataset of collision avoidance between people

We have been aided in our work on dyadic collision avoidance by a a cooperation with the laboratory Mouvement, Sport, Santé (M2S). In this cooperation, the researchers in the laboratory M2S designed and executed an experiment involving interactions between two people having crossing trajectories. Participants volunteered to perform the experiment and the study conforms to the declaration of Helsinki [START_REF] Wma | World medical association declaration of helsinki[END_REF].

The experiments were composed of over 450 runs divided near equally into five different crossing angles: 30°, 60°, 90°, 120°and 150°. The area designed for the experiment is equal to a square with length of 12 m. As can be seen in Fig. 5-1a, there are occluding walls each with three meters in length at the middle of each square side that are oriented towards its center. The walls are meant to separate participants in such way that they are not able to see all other participants at the starting point. This allowed the participants to reach a stable speed before the start of the interaction. As a consequence, one can measure motion adaptations solely caused by the interaction with another participant.

Participants were told to reach the opposite side of the experiment area while walking and avoiding any collision and were informed that they will interact with another person. Tracking the movement of people as they walk within the area of study was done with infrared cameras from Oxford Metrics (VOW, 2019). The positions of people are obtained with reflective markers, shown in Fig. 5-1b, placed on standardized anatomical landmarks in their bodies, e.g. shoulders, arms and head. These markers are then recognized by the infrared cameras and each person position can then be reconstructed in 3D at a frequency of 120 times per second as shown in Fig. 5-1c. The analysis of participants' behavior was made within what we call the "observation zone", depicted in Fig. 5-1a, this zone is defined as a circular region with three meters radius in the center of the square. Within this zone participants are able to see each other and interact to avoid collision. This region was designed in such a way as to provide sufficient space so that subjects can adapt their speed and orientation during collision avoidance.

Each run of a collision avoidance scenario involves four participants, however only two at a time will ever enter the observation zone at each run. This is necessary as in some crossing scenarios a person may see another one as soon as they are into their initial positions, as such, it is necessary to add some uncertainty to avoid possibly altering their behavior. The non-participants, as can be see in Fig. 5-1, will not enter the observation zone and thus do not participate in the collision avoidance. The synchronization of the participants initial position and start time is done automatically in order to allow for several different collision avoidance situations.

After the experiments, our task was reconstructing a cloud of points into precise human positions over time so that the motion capture data could be used. After precise position reconstruction, several filters were used into the data to remove tests with excessive noise and without collision avoidance behavior, after which a total of 202 runs remained for analysis. A complete list of the types of error and their respective amounts in the dataset is shown in Table 5.1.

Among the errors, reconstruction of people and their position was the most frequent problem and happened roughly twice as often during the afternoon than in the morning. We assume this is due to differences in illumination but no rigorous evaluation of the source of reconstruction errors was made. Additionally, situations with no risk of collision were Based on this data, our first step is to define a cost to represent the motion adaptations done by each person. Based on this cost we would then be able to show that there is a statistically significant difference in distribution of motion adaptations between roles in a given collision avoidance situation.

Collision avoidance cost function

Our goal is to use the resulting dataset of the trajectory of crossing people in order to model how people distribute their motions to avoid collision. A trajectory is defined as

π p = p p (0), p p (1), • • • , p p (t), • • • , p p (n) (5.1)
where p p (t) = (x p (t), y p (t)) ∈ R × R represents the position of agent p at time t while n represents the total number of time steps to the goal. In this section, our goal is to define, for a given pair of trajectories π p and π r representing the motion of agents p and r involved in a collision avoidance, the cost of each trajectory and the manner to calculate distribution of said cost among agents.

Energy cost computation based on social science studies

The energy expenditure of people per unit distance has been subject of much research [START_REF] Zarrugh | Optimization of energy expenditure during level walking[END_REF][START_REF] Ralston | Energy-speed relation and optimal speed during level walking[END_REF]. Based on these studies, the mean energy cost of a trajectory can be derived based on the speed [START_REF] Zarrugh | Optimization of energy expenditure during level walking[END_REF] of a person at every instant, and is calculated as

E(π p ) = n ∑ t=1 32 + 0.0050v p (t) 2 (5.2)
which represents a quadratic cost function in terms of speed v p (t) = ‖ p p (t)-p p (t-1)‖ ts at time t for the trajectory π p where ‖•‖ represents the euclidean norm function and ts the timestep duration. This quadratic function, with its coefficients defined based on experiments with people, calculates the average number of calories spent per minute per kilogram for a given speed.

A person going towards its goal without any obstacle might choose what is defined as an optimal-speed walk [START_REF] Zarrugh | Optimization of energy expenditure during level walking[END_REF] which refers to the most energy efficient (in terms of calories) walking speed for a given person. Empirical evidence found that this value for an average person is of 80 m/min or 1.33 m/s [START_REF] Zarrugh | Optimization of energy expenditure during level walking[END_REF]. For a robot, the task of finding the most energy efficiency trajectory of a person to a given goal could be defined simply as

π * π = arg min π r ∈Π r E(π r ) (5.3)
where Π r is the set of admissible trajectories of robot r to its goal -trajectories that are both safe (collision-free) and appropriate.

People do not always walk at their most energy efficient speed [START_REF] Basili | Strategies of locomotor collision avoidance[END_REF]. Depending on the situation, a person might favor arriving earlier at the goal even though this leads to an increase in total energy consumed. In order to address this issue, in the following section, we define a cost function that is optimal only when people reach their goal at their desired time while also spending their desired amount of energy. Moreover, we also determine in which manner a person speed before collision avoidance can be used to estimate both the desired speed and energy.

Time and energy as trajectory cost

In practice, people do not always walk at a certain speed even if this speed is more energy efficient, they may increase or decrease their speed to:

• decrease or increase time to arrive at the goal, which changes the energy expenditure,

• and avoid collision, which might increase or decrease energy expenditure and time to the goal.

Based on the fact that time to the goal is also an important component in describing the cost of a trajectory, we define a cost function that accounts for not only energy expenditure but on a weighted trade-off between energy spent and time elapsed to the goal. This time and energy trade-off for a person can be represented as a trajectory cost function

Γ : [R 2 , • • • , R 2 ] → R and is defined as Γ(π p ) = E(π p ) + ζ p (v des p ) • T (π p ) (5.4)
where T (π p ) is the time required to execute this trajectory and v des p is the desired speed choice for a person in case there were no obstacles to its goal, the desired speed is assumed to be constant throughout a person's trajectory. Moreover, ζ : R → R is a function of a given speed that returns a value which makes a given time energy trade-off optimal only when the agent p arrives at the goal with the desired energy and time, thus for each v des p , its value can be calculated in a three step process

Γ(π p ) = n ∑ t=1 32 + 0.0050v p (t) 2 + ζ p (v des p ) n ∑ t=1 1 (5.5) = n ∑ t=1 32 + 0.0050v p (t) 2 + ζ p (v des p ) (5.6)
Given that the desired speed was assumed to be constant throughout a person's trajectory the optimal value of ζ (•) will also be constant, thus let v p (t) = v p for every t where v p can be any speed reachable for a walking person, thus (5.8) where S(π p ) is the length in meters of the trajectory π p . We then derivate

Γ(π p ) S(π p ) = 0.0050v 2 p + 32 + ζ p (v des p ) v p (5.7) = 0.0050v p + 32 + ζ p (v des p ) v p
Γ(π p )
S(π p ) with respect to v and then set v p = v des p . Equating to zero yields

ζ p (v des p ) = 0.0050 • (v des p ) 2 -32 (5.9)
In our dataset the actual value of v des p is determined based on the speed of p before collision avoidance starts. As an example, in case p walks towards his goal before collision avoidance at a speed of v des p = 2.0 m/s that would yield ζ p (v des p ) = 2 3 . Thus, for a given v des p the value of ζ (v des p ) that makes this chosen time energy trade-off optimal for Eq. 5.4 can be calculated for any speed. The shape of the time energy trade-off function, given ζ , p ) in case one walks straight to the goal without obstacles. Thus, for each case the minimal value is reached only when the agent arrives at his goal at the desired time using the desired amount of energy. Thus, in case a person accelerates, decelerates or move its heading away from the goal in order to avoid a collision its value will not ever be minimal.

is showcased in Fig. 5-2.

This formulation represents an effort measure even for cases when the agent arrives earlier to the goal while using more energy or when it arrives later while using less energy i.e. the value of Γ(π p ) will not be minimum. More clearly, whenever a person moving on her desired speed towards her goal decides to accelerate, decelerate or change heading in order to avoid a collision the value of Γ(π p ) will invariably increase.

The value ζ p (v des

p ) is of fundamental importance for our formulation given that it defines the willingness of a person to spend energy to reach their goal sooner. For instance, if ζ is defined as zero, the agent will prefer the most cost-efficient speed. On the other hand, higher values of ζ (v des p ) progressively indicate to the agent that higher energy costs are worth, up to a point, in order to arrive sooner to his goal.

In the case where dynamic obstacles with potential collision risk are involved, more specifically people, one can increase or reduce their speed and also change their heading to avoid a collision. This in turn can change their original balance between the amount of energy invested and the time to the goal.

Finally, each person has a different trajectory energy cost function and thus a different

ζ (v des p ). In the current iteration of our formulation, the most energy-efficient speed is set as the grand average of 1.33 m/s [START_REF] Zarrugh | Optimization of energy expenditure during level walking[END_REF].

From trajectory cost to collision avoidance effort

As we established in Sec. 5.3.2, in our cost function a person that has to avoid a collision will invariably change its time energy trade-off to non-optimal values. This change is what we define as collision avoidance effort.

The trajectory of an agent p to its goal in the absence of obstacles is named baseline trajectory and denoted by π base p . The baseline motion can be determined from our dataset by combining the speed of the person before collision avoidance (desired speed) and their final position (goal). This baseline allows us to establish a comparison between their desired motion and their motion given collision avoidance with another person.

The collision avoidance effort can be calculated by comparing the weighted change in energy and time to collision of the baseline with respect to the actual trajectory. Thus, let ∆E(π p ) = E(π p ) -E(π base p ) and ∆T (π p ) = T (π p ) -T (π base p ) represent, respectively, the change in energy and time between π p and π base p . Thus, we represent collision avoidance effort as

F(π p ) = ∆Γ(π p ) = ∆E(π p ) + ζ (v des p ) • ∆T (π p ) (5.10)
The value F(π p ) will only be minimal when the person arrives in his/her goal with both the desired time and energy. In this case, F(π p ) will be zero.

Given the aforementioned formulation, the Effort Distribution Coefficient (EDC) of a given agent p, that is, their contribution to collision avoidance in relation to another agent r, represented as β p,r , can be directly calculated using

β p,r = F(π p ) F(π p ) + F(π r ) (5.11)
This formulation enables comparison of the proportion of effort p was responsible for in a given collision scenario when compared to total effort invested by both r and p. Using such formulation, our next step is then to use it within our dataset to evaluate whether there is a pattern in the distribution of collision avoidance effort between people and what situational factors can predict its distribution.

Collaborative nature of collision avoidance

Given a measure of human effort in terms of energy and time to goal, presented in Sec. 5.3, our objective is to establish a relationship between this cost function and actual human Figure 5-3: Proportion of effort that was done by the person who crosses in front, that is β front,beh , with respect to total effort required to avoid a collision. In situations that require higher total collision avoidance effort its distribution shifts the majority of the effort towards the person crossing behind. Boxplots in blue indicate that there is a significant difference between the contribution of the person crossing in front and the person crossing behind (p-value<0.05) and in red indicate no significant difference (p-value>0.05). Values are considered outliers when outside 99.3% coverage.

data. Moreover, based on the relationship found, replicate this distribution of effort using data from our dataset.

Distribution of collision avoidance effort in people

Our objective can be summarized as estimating, based on our dataset, the collision avoidance effort for both the person crossing in front and behind and, based on this estimation, allow a robot to replicate effort distribution expectations during collision avoidance.

In order to evaluate whether there is a statistically significant difference in distribution of collision avoidance effort between the person crossing in front and the person crossing behind, a paired t-test is used. To that end, the steps taken can be enumerated as 1. Skip trials with any of the errors mentioned in Table 5.1.

2. Partition trials with respect to their total collision avoidance effort. Compare expectations of people regarding effort distribution in scenarios of varying complexity.

3. Compare collision avoidance effort and its distribution between the person crossing in front and the person crossing behind using a paired t-test for each partition.

Let π front and π beh be, respectively, the trajectories of the person crossing in front and the person crossing behind within the zone of observation. Our trials are labeled based on total collision avoidance effort which is represented as F(π front ) + F(π beh ). These trials are then separated into three partitions based on the total collision avoidance effort:

• Scenarios where considered to require small amount of motion adaptations when F(π front ) + F(π beh ) < 0.055

• Scenarios with medium amount of motion adaptations when 0.055 ≤ F(π front ) + F(π beh ) < 0.110

• Finally, harder scenarios with high amount of motion changes whenever F(π front ) + F(π beh ) ≥ 0.110

Our results, shown in Fig. 5-3b, indicate that the person crossing behind contributed more to collision avoidance task when the total collision avoidance effort in scenarios with medium or high amount of motion adaptations. There was no significant difference in scenario with small amount of motion changes. Thus, whenever a relatively small amount of effort is necessary to avoid a collision the distribution of effort still varies but without bias towards a particular role.

In short, from this data, one can highlight the following general patterns:

• As the total collision avoidance from increases, as seen in Fig. 5-3a, the chance that the person crossing in front would be responsible for most of the effort decreases. In the scenarios with highest collision avoidance effort the person crossing behind was responsible for most of the effort in the large majority of scenarios

• In situations with a collision avoidance effort near zero difference in collision avoidance effort invested by people, shown in Fig. 5-3b, is not statistically significant. This points towards an equal distribution of effort between people in scenarios with smaller collision avoidance effort.

• Also in Fig. 5-3b, it can be seen that the mean proportion of collision avoidance effort required for the person crossing behind increased whenever total collision avoidance effort also increased.

Based on these patterns, our objective is to define what situational factors can be used to estimate the required amount of collision avoidance effort to prevent future collision. Based on this prediction we would also be able to calculate the expected distribution of effort between people. Finally, this expected distribution can then be replicated in a robot.

Estimating effort distribution with situational factors

The concept of collision avoidance effort allows us to determine effort distribution between two trajectories of people in a given scenario. Evidently, a robot that intends to replicate this effort distribution has to do so based solely on the initial configuration of both agents before collision avoidance starts.

When collision avoidance between agents starts the effort distribution should be estimated and used for the remainder of the collision avoidance, that is, from t i up to t f that denote, respectively, the start and end of the collision avoidance. To estimate the effort for each role in a given collision scenario we model it based on four situational factors (see discussion in Section 2.4 for details) that serve as statistical predictors:

1. Crossing angle, denoted as φ , which is the angle formed by the crossing paths of both agents, as defined by φ = |π -|θ frontθ beh || where θ front and θ beh are the global heading of the person crossing in front and the person crossing behind respectively.

2. Difference in initial speed between the person crossing in front and the person crossing behind, which is given by ∆v = v des front -v des beh where v des front represent the velocity of the agent crossing in front and v des beh of the agent crossing behind.

3. Deviation from baseline bearing angle, denoted as z = α front,beh -φ 2 where α front,beh , is the bearing angle from the perspective of the person crossing in front in relation to the person crossing behind.

4. Time to collision is represented by the time to minimum distance, as shown in Sec.

2.1.1. A collision is considered possible whenever Minimum Predicted Distance (MPD) is less than one meter.

Our objective is to associate these four situational factors, most of which are shown in Fig 5-4, with an estimation of collision avoidance effort for each role. To produce such estimation a Generalized Linear Model (GLM) was chosen, which is described in detail in Appendix B. The GLM was chosen, instead of a linear regression, as it allows for constant change in predictors (situational factors) to be able to cause non-constant change in response. This is important as the increase in total collision avoidance effort causes a nonconstant increase in the proportion of effort done by the person crossing behind.

Given this choice, a GLM using a Binomial distribution and a logit link function was used. This combination of distribution and link function has a shape similar to a multidimensional sigmoid.

The four situational factors were fitted to the collision avoidance effort of each role using GLM with p-value < 0.05. The results obtained for the both roles are valid only within the region where effort is bigger than 0.035, given that the spread of effort distribution when absolute collision avoidance effort is small would be too high to allow for reliable prediction. Thus, let Ffront (φ , ∆v, z, ttc) = g -1 ( β front X) and Fbeh (φ , ∆v, z, ttc) = g -1 ( β beh X) represent, respectively, an estimation of the collision avoidance effort for the agent crossing in front and the agent crossing behind where g -1 (•) is the inverse link function, the explanatory variables are X = {1.0, φ , ∆v, z, ttc} and the coefficient values found through maximum-likelihood are β front = {-4.91735, 0.00374, -0.02106, -0.00056, 0.07100} for the person crossing in front while for the person crossing these are β beh = {-3.22311, 0.01466, -0.13971, -0.00301, -0.11598}.

An example of effort difference between both roles can be seen in Fig. 5-5, where the evaluated model indicates that, in average, the upper bound for effort invested by the person crossing in front remains nearly constant while for the person crossing behind it increases unbounded as the collision avoidance problem becomes more difficult.

As stated in Sec. 5.4.1, in cases which require relatively small amounts of total effort the spread of the effort distribution is high, as such, the effort distribution in these cases is not consistent with the values predicted by our generalized linear model.

Given this estimation of collision avoidance effort for each agent, a robot can then replicate effort distribution expectations by approximating the value of EDC, calculated as

β front,beh ≈ βfront,beh = Ffront (φ , ∆v, z, ttc) Ffront (φ , ∆v, z, ttc) + Fbeh (φ , ∆v, z, ttc) (5.12)
Both Reciprocal Velocity Obstacles (RVO) and our model can be applied to multiple people by considering all possible pairwise combinations of agents. However, as our dataset with people is restricted to dyadic interaction we omit such experiments due to lack of a baseline.

Simulated experiments

Simulated experiments were performed with two main goals in consideration. The first is evaluating the impact of shared effort in generated trajectories and the second is to show whether shared effort during collision avoidance replicates behavior of people.

Navigation approach using custom effort distribution

Determining how change in effort distribution affect generated trajectories requires a navigation approach that can be modified in order to accommodate changing proportions in effort distribution. Given that the concept of distribution of motion adaptations to guarantee collision avoidance is paramount in RVO, this approach was chosen as the navigation method. A detailed description of RVO was given in Sec. 4.1.2. In comparison with other methods, such as Social Force Model (SFM), an advantage of RVO is that the proportion of effort distribution can be controlled with a single variable. Our objective is then to associate the value of this variable with EDC to obtain distribution of motion adaptations that respect effort distribution given by our method instead of its usual equal share as depicted in Figure 56.

Consider a situation where two agents q and p, with desired velocities v des q and v des p will eventually collide in case of no change in their current velocities. For these cases, RVO finds the smallest change in the relative velocity (v des q -v des p ) that avoids a collision between them (van den Berg et al., 2011), this is given by u as 5.13) where ∂ VO τ q|p is the set of changes in relative velocity that are in the threshold between collision and no collision -the minimum change in relative velocity that avoids a collision. Commonly, RVO shares the change in relative velocity equally between the two agents (van den Berg et al., 2011), that is, 1 2 u for each. However, based on previous works on human-human interaction, when an agent represents a model of a person's behavior this is not always the correct approach. As such, in our work the value of EDC instead of the standard equal share.

u = ( arg min v∈∂ VO τ q|p ‖ v -( v des q -v des p )‖) -( v des q -v des p ) (
An important issue is the large variance in effort distribution in small collision avoidance effort situations (discussed in Sec. 5.4.1). Given that RVO requires effort to be reciprocal, it is not evident how to translate this optional cooperative effort into the model. Thus, collision avoidance scenarios that require smaller total collision avoidance effort are set to have equal effort distribution while when total collision avoidance increases the effort distribution is shifted to the actual model-based effort distribution value. Thus, we represent the desired behavior as

f (φ , ∆v, z, ttc) = 1
1 + e -γ( Ffront (φ ,∆v,z,ttc)+ Fbeh (φ ,∆v,z,ttc)-c) (5.14)

RVO-EDC(φ , ∆v, z, ttc) = 0.5 + ( βfront,beh -0.5) f (φ , ∆v, z, ttc) (5.15) where c = 0.03 and γ = 260 are defined based on the empirical data as to allow for smooth transition from equal distribution to using EDC depending on the total collision avoidance effort.

Effort distribution impact in generated trajectories

Changing the standard distribution of effort in RVO impacts the generated trajectories. In order to assess such impact this section compares the original trajectories from people against both the standard RVO and our modified RVO using our effort distribution. As seen in Sec. 5.5.1, whenever total collision avoidance effort is small our approach simply replicates standard RVO behavior. As such, this section focuses on situations where total collision avoidance effort is larger than 0.35 units.

In our tests, shown in Fig. 567, in a large majority of the cases examined our approach allowed the agent crossing in front to the reduce their contribution to avoid collision. This is important given that, as seen in Section 2.2, a person crossing in front generally accelerates and changes heading to avoid collision. Reducing the potential contribution for the agent crossing in front allows for more human-like trajectories and also behaviors that are perceived as safer due to more natural accelerations.

A limitation of our current RVO-approach is a consequence of the sometimes hard to predict behavior of people. In our dataset and as discussed in Sec. 2.2.2, people were sometimes shown to reverse their crossing order during collision avoidance. As is shown Total effort in Fig. 5678, this can cause differences in generated trajectories to reproduce using RVO.

E[V our ] E[V rvo ] E[V rvo ] -E[V our ] F(π p ) + F(π r ) < 0.

Quantitative evaluation of differences in effort distribution

Although a visual presented of the change in collision avoidance behavior of a select number of trajectories is important, a more general evaluation of differences effort distribution is necessary in order to allow for a more general conclusion.

To that end, let V our = β front,beh -βfront,beh denote the absolute difference between the actual EDC and our predicted EDC while V rvo = β front,beh -1 2 denotes the absolute difference between the actual EDC and standard RVO.

In order to evaluate the expected difference in values of V our and V our we first sample 80 collision avoidance situations from our dataset. Afterwards, the comparison in terms of actual and expected effort distribution are then shown in Table 5.2. The results, partitioned with respect to effort in the same manner as in Fig. 5-3b, show that our approach provides little improvement with respect to standard RVO whenever total collision avoidance effort is smaller than 0.055. However, whenever total collision avoidance effort is larger than this threshold our approach significantly improves replication of effort distribution between agents during collision avoidance. To further confirm this pattern, we observed that among the scenarios with the highest amount of total collision avoidance effort and found that, the difference between predicted and actual effort distribution was lower than five percentage points in several scenarios.

Experiments in ROS

In order to evaluate collision avoidance behavior with more realistic robot models we replicate some of our experiments using Robot Operating System (ROS) [START_REF] Quigley | Ros: an open-source robot operating system[END_REF] with a plugin that implements RVO behavior within ROS named "collvoid" [START_REF] Claes | Collision avoidance under bounded localization uncertainty[END_REF].

Both agents were chosen to be represented as a PR2 robots (PR2, 2019). Robots share their position with each other, however, collision avoidance starts only after recognizing each other using a laser sensor.

Given this robot model our first objective was to evaluate whether their realistic motion constraints still allowed for asymmetric effort distribution. For that reason, our first experiment relied on manually choosing values for the effort distribution. The results, presented in Fig. 56789, shown a significant difference in collision avoidance behavior depending of the specific effort distribution that was chosen.

The second step of our ROS validation requires establishing a comparison between predicted effort distribution in our simulated cases with the baseline obtained from the dataset. Although the smaller frame of the robots required a smaller amount of motion adaptations in comparison to people, robots were still able to share effort in a manner similar to what was predicted by our model. In order to better highlight the differences, situations with higher collision avoidance effort were shown in Fig. 5678910.

As a validation of more extreme cases, situations where one robot is approaching the other from behind are tested. In these cases and as exemplified in Fig. 5-11, it can be seen that, even though both robots are made aware of each other, the agent in front does not share collision avoidance effort with the agents coming from behind due to our model. In all tested cases the model predicted negligible effort for the agent in front.

Discussion

People do not always share collision avoidance effort in the same manner, factors such as time to collision and crossing angle affect the proportion each role (crossing in front or behind) is responsible for. Due to a greater relative importance of situational factors, as discussed in Sec. 2.1.3, the impact of personal factors in human behavior, such as with culture [START_REF] Chattaraj | Comparison of pedestrian fundamental diagram across cultures[END_REF] and with gender [START_REF] Van Basten | Exploiting motion capture to enhance avoidance behaviour in games[END_REF], is not taken into account.

Based on hundreds of collision avoidance situations between people, we evaluated what situational factors influence the collision avoidance effort distribution in several distinct scenarios. From this, a definition of collision avoidance effort was created and also a model capable of predicting effort distribution. The model shows a clear increase in the relative proportion of effort for the agent crossing behind as the total collision avoidance effort increases. The model was tested in simulated experiments and its result reveals a difference in generated behavior when compared to standard RVO. This difference is more pronounced when a given collision situation requires higher amounts of collision avoidance effort. The generated motions were also compared with human trajectories in order to evaluate consistency of the generated motions with actual human data.

It is important to highlight that other factors can influence the manner in which a robot should share effort to others. For instance, a robot can and should yield to a child, given that its awareness of social rules and expectations is not certain when it comes to collision avoidance, even when situational factors would indicate otherwise. Another important factor is that people do not always respect crossing order. Planning collision avoidance motions that depend on this premise can ultimately lead to collision when a robot relies on a person always behaving in a particular manner. In order to account for and alleviate the consequences of a person not respecting crossing order a novel collision avoidance approach is necessary and is presented in Chapter 6.

Chapter 6

Human-robot collision avoidance under near symmetry A robot can plan a collision avoidance motion while seeing the person as a simple moving obstacle. However, as is seen in the previous chapter, a person usually shares collision avoidance effort while assuming to be in a particular role (crossing in front or behind) when avoiding collision. An important research problem arises as a consequence of such collaboration: is collaboration during collision avoidance always effective? Before answering this question, it is important to first define the concept of effective collaboration. In the context of collision avoidance, in Chapter 4 collaboration during collision avoidance is defined in terms of complementary motion adaptations with the shared purpose of avoiding future collision between agents. Furthermore, collaboration can be called effective whenever motion adaptations by all agents are complementary for collision avoidance. Given this background, effective collaboration can happen whenever agents either assume opposite roles (choose the same homotopy class) or when only a single agent attempts to avoid future collision (the other would behave as a moving obstacle).

In this chapter, we focus specifically on the case where both agents attempt to contribute to future collision avoidance. This is justified as in the previous chapter it is shown that, in average, both roles contribute to collision avoidance. Thus we evaluate first whether collaboration between agents is always effective and then we define the boundary that predicts when ineffective collaboration can happen and finally present an approach to mitigate the potential negative consequences of such event.

Ambiguous role during collision avoidance between people

We hypothesize that in some situations people are unable to perceive the correct crossing order decision, which might lead them both to incorrectly choose the same crossing order i.e. a decision detrimental to collision avoidance. In this section, we first present a manner to visualize situations where the temporal progression of collision avoidance is negatively affected, afterwards we present how this negative impact in collision avoidance progression can be represented as a new phase during interaction between people.

Representing negative impact in collision avoidance progress

Our first step in order to represent situations where collision avoidance is not done effectively requires visualizing these decisions in our human collision avoidance dataset. Even though Minimum Predicted Distance (MPD) and Signed Minimum Predicted Distance (SMPD) can be used to correctly assess collision avoidance progress, it may incorrectly represent a collision problem as solved in cases where agents choose the same crossing order. For instance, in a dyadic collision avoidance scenario whenever both agents decided to stop in order to avoid collision, both the MPD and SMPD would increase to safe values indicating that collision avoidance is solved. However, in such a situation both agents still cannot move towards their goal in their original velocity without risking, once again, collision. In order to better visualize situations where people reverse their crossing order or take actions that have a negative affect on the temporal evolution of the collision avoidance, we modify our MPD formulation to obtain a monotonically increasing function whenever collision avoidance is solved effectively, named Minimum Predicted Distance with Goal Heading (MPDH) and defined as

MPDH(t) = ∞ min l=t ‖( p r (t) + v des r (t) • (l -t)) -( p p (t) + v des p (t) • (l -t))‖ (6.1)
where v des r is the agent r desired walking velocity at this time if there were no obstacles. This formulation considers the minimum distance considering the hypothetical scenario where the agents have their desired velocity towards the goal. In this sense, it represents the collision potential in terms of its impact in an agent's ability to head towards his goal at his desired speed. This formulation, in contrast with MPD, depends on having the complete trajectories, as in our case the goal of each agent and their desired speed (before collision avoidance) can be easily determined. This measure is used to evaluate human trajectories obtained in our dataset, as can be seen in Fig. 6-1, in order to determine the impact of crossing order changes in the progress of the collision avoidance.

We can observe that, in Fig. 6-1c, the MPDH is not always monotonically increasing. In this particular case, as soon as agents are able to perceive the correct crossing order the MPDH starts to increase monotonically.

Phases of collision avoidance with ambiguous role

Collaboration is not always effective for collision avoidance. In some situations, people people may assume the same role 1 . Within the standard social science depiction of the human collision avoidance process described in Sec. 2.1.2, this would indicate that the reaction phase is not always effective. To better characterize this behavior we split the reaction phase into two phases yielding a total of four phases, defined as 1. Observation implies recognizing the future collision scenario. This definition is unchanged from Sec. 2.1.2.

2.

Negotiation is an optional phase where both agents attempt to avoid collision through a given set of motions but are not necessarily able to perceive their roles i.e. who crosses in front and who crosses behind; this in turn causes the collision avoidance to not progress, even though actions are being taken with that objective. For instance, when two agents decelerate at the same time attempting to establish the role of an agent crossing behind.

3.

Avoidance is a phase where both agents recognize their roles in the collision avoidance and take definitive action to avoid the collision. Thus, the agents use their motion more efficiently and more effectively to avoid a collision.

4.

Regulation is the phase where the agent maintain a stable MPD until minimum distance is reached. This definition unchanged is also unchanged from Sec. 2.1.2.

Given these phases, the objective of our approach is to minimize the time spent on the negotiation phase. Our intention is to minimise the period where the agents are taking ineffective actions by controlling the manner in which agents avoid collision with each other.

In other words, our approach attempts to reduce the chance that agents find themselves continuously in a situation where the collaborative crossing order decision is not evident.

Boundary in choice of crossing order

In collision avoidance situations with ambiguous crossing order our objective is to minimize the time spent in the negotiation phase. To minimize the duration of this phase, one must consider the situations where people may misjudge their crossing order.

We refer to situations in which crossing order decision of people is consistent over repeated initial conditions as near-symmetric scenarios. The concept of near-symmetry is formally defined in the following subsection which allow us to evaluate the boundary that separates an ambiguous collision avoidance situation from a scenario where a person's crossing order is evident.

Formalizing the concept of near-symmetry

The concept of homotopy class decision of an agent, described in Sec. 2.3, represents the side in which agents cross each other. Trajectories within the same homotopy class can be continuously deformed into each other. In order to avoid a collision effectively agents must choose to cross each other on the same side.

The concept of crossing order can be used as a basis to predict, at any given time t, the homotopy class decision of an agent. However, attempting to directly use this information to determine collision avoidance motions is insufficient. The reasons for this can be contextualized given a direct representation of such predictor, presented as

Θr,p (t) =                    +π or -π, if αr,p (t) = 0 +π, if α r,p (t) ≥ 0 and αr,p (t) > 0 +π, if α r,p (t) < 0 and αr,p (t) > 0 -π, if α r,p (t) ≥ 0 and αr,p (t) < 0 -π, if α r,p (t) < 0 and αr,p (t) < 0 (6.2)
which can then be simplified to

Θr,p (t) =          +π or -π, if αr,p (t) = 0 +π, if αr,p (t) > 0 -π, if αr,p (t) < 0 (6.3)
From this formulation, it is possible to verify that ambiguity can occur in two scenarios: whenever α r,p (t) ≈ 0 and thus α p r (t) ≈ 0, that is, a possible (near) head-on collision, and in the (near) symmetric cases when α r,p (t) ̸ ≈ 0 and αr,p (t) ≈ 0. In both of these scenarios each person is met with a situation where +π and -π are possible solutions. As a consequence, in the space of solutions of these ambiguous scenarios, denoted as Θr,p (t) × Θp,r (t) = {{π, π}, { -π, -π}, {π, -π}, { -π, π}}, people may try to pass each other on the same side or may incorrectly try to pass each other in opposite sides, which will negatively affect their effort to avoid future collision which may, for instance, decrease their MPD. In both ambiguity scenarios, the uncertainty over crossing order depends on the value of α, our objective is to predict the uncertainty associated with this boundary, evaluate the potential consequences of this uncertainty in generated motions and, finally, minimize the risk of collision while allowing for effective collaboration. Reactive collision avoidance approach whenever agents incorrectly choose the same crossing order. Point in red is the collision in case of no change in trajectory. Collision point in orange happens if the agents plan collision avoidance only once. Collision in the blue point when both agents continuously choose to attempt to cross behind. Whenever agents continuously believe they cross in front they reach a stable forward motion without ever colliding with each other or reaching their goal.

Estimating crossing order uncertainty based on data

Our approach relies on predicting the behavior of agents when they are avoiding each other even in the case of ambiguous crossing order. In Fig. 6-2 we depict some possible trajectories for reactive collision avoidance approaches in case crossing order mismatches happen continuously. To complement these results, in Sec. 6.4, we compare this result with our approach.

The derivative of the bearing angle α is a strong predictor of crossing order, as shown in [START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF]. However, the role of each agent in a collision avoidance situation is not always clear. In this section, our focus is on first establishing a relationship between α and the certainty in crossing order determination using the dataset presented in Chapter 5 from our collaboration with the laboratory Mouvement, Sport, Santé (M2S). Our objective is to find what is the chance that in the interval between [t i ,t f ] the predicted crossing order changes, that is, the probability of Θ(t

i ) ̸ = Θ(t) for some t ∈ [t i ,t f ].
The results, fitted to a sigmoid S(z) = 1 1+e -a(z-b) with parameters a = 39.936914 and b = -0.000037, are shown in Fig. 6-3 and indicate that, at t i , if α approaches zero the likelihood of the crossing order changing within a given collision situation increases. As an extra measure of certainty, to guarantee this is not caused by reconstruction error in the position or heading, we manually evaluated the situations in which crossing order changed and verified that in most cases collision avoidance actions for agents, in terms of speed and heading changes or lack thereof, when observed in conjunction, are initially detrimental to This sigmoid is fundamental for our approach, as this allows us to approximate what are the odds that agents will switch their crossing order from its currently perceived value. This includes situations where agents perceive crossing order incorrectly or have a particular interest in assuming a particular role. Our objective is then to determine a collision avoidance approach that accounts for this uncertainty while minimizing the chance of agents continuously choosing the same crossing order.

Collision avoidance motion for uncertainty mitigation

A collision avoidance approach that is able to deal with near-symmetry scenarios must understand how to accommodate the main source of uncertainty: the derivative of the bearing angle. In this sense, our approach attempts control the future value of the derivative of the bearing angle in such way that • In the case where both agents initially choose the same crossing order, the derivative of the bearing angle between the agents in the next decision step will allow them to correctly assess crossing order;

• the range of motions explored that permit collision avoidance is proportional to the uncertainty of crossing order. More uncertain situations may require larger heading and speed changes.

These requirements would make it possible to minimize the amount of time within the negotiation phase while minimizing the amount of additional motion adaptations. To that end, our approach described in this section provides a solution to both of the requirements listed above while planning collision avoidance robust to near-symmetry in a trivial amount of computational time.

Impact of confidence in determination of crossing order

In our work, we attempt to establish effective collision avoidance between agents in symmetric scenarios in up to n decisions, with agents taking two decisions per second. Effective collision avoidance means that both agents choose different crossing orders to avoid each other.

To that end, it is important to calculate the probability of correct collaboration 𝒟 that would allow for Λ confidence in resolving crossing order after n consecutive attempts. In our work we define 95% as an acceptable Λ value. To find the value of 𝒟 we equate the chance of n consecutive failures with 1 -Λ, as 6.4) which yields

1 -Λ = [1 -𝒟] n (
𝒟 = 1 - n √ 1 -Λ (6.5)
This means that, at each time step, the agent should attempt to guarantee that the chance of resolving crossing order is at least 𝒟. As seen in Sec. 6.2.2, crossing order certainty can be calculated using 𝒮( αr,p (t)), as such, at this time step in case 𝒟 ≤ 𝒮( αr,p (t)) the optimal collision avoidance action would generally suffice. However, our approach also anticipates situations with ambiguous crossing order by controlling the derivative of the bearing angle in an attempt to guarantee that, in the next time step, the chance of collaboration will be, in average, enough to achieve the desired confidence over n steps.

Obtaining a desired confidence with random uniform sampling

Consider that the robot r decides to avoid the collision with an agent p by changing its velocity to v new r , this decision is made based on the current velocity of the other agent, which we denote as v p (t). This motion, in case of no change in the behavior of p, would yield αnew r,p . Similarly, agent p would use a similar logic to obtain a possibly distinct2 αnew p,r . Based on Eq. 2.2, the combined effect of these individual velocity changes on the instantaneous value of the derivative of the bearing angle can be calculated using αnew r,p + αnew p,r . Whenever agents incorrectly choose the same crossing order αnew r,p and αnew p,r will have distinct signs i.e. one will be positive and the other will be negative. Our objective is to calculate the probability 𝒫 that αnew r,p + αnew p,r in the next decision step will be equal or larger than a given threshold κ. This would guarantee a certain confidence that even if agents at first incorrectly choose the same crossing order the crossing order would not remain ambiguous at the next decision step.

The desired value of 𝒫(z) where z = αr,p (t) at current time step can be calculated by equating the probability of two incorrect collaborations at the current and subsequent decision step to the current 1 -𝒮( αr,p (t)) and the subsequent one where αnew r,p + αnew p,r is not larger than κ, with

𝒫(z) = 1 - (1 -𝒟) • (1 -𝒟) 1 -𝒮(z) (6.6)
Our final steps are then to determine the threshold value κ and to determine the manner in which one can guarantee | αnew r,p + αnew p,r |≥ κ with average probability 𝒫(z). To this end, let 𝒳 be a random variable uniformly distributed over the interval [0, ℒ]. From this random variable we select two points 𝒳 1 and 𝒳 2 . The distance between these points, denoted as Y = |𝒳 1 -𝒳 2 |, has an average value of M = E[Y ] = L 3 (see Appendix C for details) where E[•] is the expected value. Due to the locally linear shape of its function, we assume that a sample from Y that is m units away from the mean approximately respects the equality 𝒫(M) = 𝒫(M-m)+𝒫(M+m) 2 , this would mean that 𝒫(E[Y ]) = E[𝒫(Y )]. This approximation allows us to establish that with M = κ we can finally determine the value of κ using the inverse of the sigmoid function (logit) presented in Sec. 6.2.2, denoted as

𝒮 -1 (w) = b + 1
a log( w 1-w ), as a function of the desired probability of collaboration in the next time step with κ = 𝒮 -1 (𝒫(z)).

With these elements we can choose motions that respect the relation | αnew r,p + αnew p,r |≥ κ with average probability equal to 𝒫(z) by sampling αnew r,p from a uniform distribution with interval length ℒ = 3κ.

The relationship between n, αr,p (t) and ℒ are shown in Fig. 6-4. As n increases the size of ℒ decreases until it it reaches zero which signifies that the agent is guessing crossing order based on just its current αr,p (t). This means that whenever αr,p (t) = 0 both agents would be choosing crossing order with odds no better than chance unless ℒ > 0. (a) Head-on future collision with different initial speed. Crossing order is not defined in these cases.

Generating collision avoidance motion

In the context of dyadic collision avoidance, our premise is that each individual agent will do its best to avoid future collision while preserving crossing order. The range of actions an agent can perform is limited by their maximum linear and angular velocity. Considering these constraints, each individual agent will attempt to minimize the change in their desired velocity v des r (t) that can avoid the future collision. This is represented as

v * r = arg min v∈ℱ p r v -v des r (t) (6.7)
where ℱ p r is the set of velocities for r where MPD of r with respect to p is larger than the threshold for collision and also respects crossing order i.e. attempts to guarantee that Θp r (t i ) = Θp r (t) for all t ∈ [t i ,t f ] where t i and t f represent, respectively, the start and end of the collision avoidance However, as is shown in Sec. 6.2.2, crossing order can be misjudged which can have a detrimental impact on collision avoidance. As such, first we define an additional constraint A comparison between a standard approach and our approach when two virtual agents attempt to avoid collision with each other in a near-symmetry situation in which one agent misjudges his crossing order. Let ∆v x and ∆v y be a change in velocity in x and y axis. on v based on the αnew r,p it would generate, represented as αnew r,p = R( αr,p , α+ r,p ) (6.8) where R( αr,p , α+ r,p ) is a uniformly distributed random value in the interval defined by αr,p and α+ r,p , which represent, respectively, the lower and upper bound in possible values of the derivative of bearing angle for r with respect to p that can avoid collision in a given crossing order. To guarantee the desired confidence, it is fundamental that ℒ ≤ α+ r,p -αr,p but it is only necessary to select a subset of the interval α+ r,p -αr,p that has ℒ length. In order to facilitate visualization of the change in collision avoidance motion caused by constraining the value of αnew r,p , examples of possible collision avoidance motions with several distinct choices of αnew r,p , sampled from a discrete subset of values within an interval of size ℒ, are shown in Fig. 6-5. Moreover, the manner in which constraining the αnew r,p allows for more efficient selection of collision avoidance velocities in near symmetry scenarios is shown in Fig. 6-6.

Based on these components, we use an optimization approach named Sequential Least Squares Programming (SLSQP), originally presented in [START_REF] Kraft | A software package for sequential quadratic programming[END_REF], to generate collision avoidance velocities that respect crossing order. In our experiments, we have used the implementation provided in [START_REF] Kraft | Algorithm 733: Tomp-fortran modules for optimal control calculations[END_REF], as it can handle any combination of bounds, equality and inequality constraints.

Given perceived safety and kinematic constraints, it is possible that ℒ ≥ α+ r,p -αr,p , in these cases the agent would still attempt to resolve the collision with reduced confidence. However, when time to collision is below one timestep with ℒ ≥ α+ r,p -αr,p the agent yields as it does not have the required confidence for human-like collaboration. These situations are more frequent whenever agents are too far away (time to collision above six seconds) or too close (time to collision below one second).

In situations where crossing order has already a confidence value higher than Λ, which means that ℒ = 0, it is possible to preserve crossing order even when one agent cannot contribute to avoid a collision (or its contribution would be insufficient). For instance, as shown in Fig. 1-1b, in many situations the agent crossing in front is unable to accelerate further or change heading in a manner that preserves crossing order and they are thus unable to contribute to collision avoidance. Nonetheless, in scenarios with clear crossing order the agent crossing in front would be able to rely on the agent crossing behind to avoid collision even without any cooperation.

In any similar case, it is fundamental that crossing order is unambiguous as otherwise the agent crossing behind could incorrectly perceive himself as crossing in front. This would ultimately result in collision if both agents are unable to contribute to collision avoidance while trying to cross in front.

Experimental validation

Evaluating whether agents can avoid collision in near symmetry scenarios requires analysis of data from the agents' motion in situations with ambiguous crossing order. To that end, several simulated experiments analyzing different aspects of our approach are described in this section.

In our experiments, a holonomic motion model is chosen for the robot but the change in heading direction θ r between decision steps is bounded asπ 2 < θr < π 2 (rad/s) during collision avoidance to allow for more predictable motions. Similarly, the maximum speed of both agents is set as v max Finally, to avoid sudden turns during collision avoidance, which would negatively affect motion predictability for people, robot motions are smoothed using cubic splines. r,p -α+ r,p is larger than ℒ, are marked in bold. As crossing order is chosen randomly it can affect the length of αr,p -α+ r,p in similar scenarios (crossing behind usually allows for larger interval). In the case with 120°crossing angle a smaller n is used.

Impact of linear and angular constraints on motion

Although we establish the condition ℒ ≤ [ αr,p , α+ r,p ] for Λ confidence in effective collision avoidance, it is important to evaluate when, in practice, the robot can obtain a reasonable length of the interval [ αr,p , α+ r,p ] when the constraints in both v max r and θr are taken into account.

To that end, several random variations of collision avoidance scenarios are simulated over two crossing orders. The results, calculated considering Λ = 95% and showcased in Table 6.1, indicate that, when time to collision is small, the length of the interval [ αr,p , α+ r,p ] also decreases. In these situations, collision avoidance requires sharper changes in speed and heading, this means that a smaller range of motions that are still able to avoid collision can be achieved.

In our analysis it is shown that in smaller crossing angles three decisions can be necessary to achieve confidence larger than at least 90%. In contrast, collision scenarios with crossing angle of 120°allowed us to utilize up to n = 2 while maintaining Λ confidence, even though the situations for both crossing angles are generated with the same random process, this indicates that smaller changes in heading and speed generated larger changes in the derivative of the bearing angle when crossing angle is higher.

Although not directly accounted for in this evaluation, field-of-view consideration, such Comparison of ideal scenarios where people always respect crossing order to our approach where ineffective collaboration is possible. Our collision avoidance approach mitigated the negative consequences of such event. Continuous lines indicate ambiguous crossing order while dashed gray lines indicate crossing order is no longer ambiguous. as is done in [START_REF] Ondrej | A synthetic-vision based steering approach for crowd simulation[END_REF], could reduce the amount of situations with larger crossing angle (e.g. 150°) where near symmetry mitigation is necessary.

Collision avoidance trajectories under near symmetry

In order to assess whether generated collision avoidance motions properly mitigate the potential negative impact of ambiguous crossing order, a dozen collision avoidance scenarios where generated for each of the four tested crossing angles, these are: 0°, 30°, 60°and also 90°.

A comparison baseline with our approach is established using the collision avoidance behavior of RVO (van den Berg et al., 2011) which has seen extensive use in the literature. As can be seen in Fig. 67, RVO is only able to reproduce collision avoidance motions where crossing order is respected. Our approach accounts for the possibility that agents misjudge crossing order in near symmetry scenarios.

The negative impact of ineffective collaboration in both agents ability to head towards their goal can be visualized with MPDH. In Fig. 678, an incorrect choice of crossing order can cause MPDH to increase less efficiently or even decrease i.e. negatively affecting their efforts to avoid collision.

In most cases, effective collaboration started after at most three decisions. In under 7% of the evaluated cases, the near-symmetry situation is not solved and both agents stopped when time to collision is below one second. Do note, however, that as situations are generated with some degree of randomness the available time for effective collaboration varied.

Discussion

Differences in effort distribution can explain one part of people's collaborative approach to collision avoidance. Another part is the choice of homotopy class. In this chapter we have shown how to predict, with sufficient accuracy, the homotopy class decision of an agent based on one single situational factor: the derivative of bearing angle. Moreover, based on empirical data, we have also shown how to approximate the uncertainty around the boundary between one homotopy class decision and the other.

The core concept of our approach to tackle near symmetry scenarios during collision avoidance is using communication through motion. The agent samples from a uniform distribution of size ℒ the value αnew r,p in relation to the person's current perceived motion to have Λ confidence that effective collision avoidance will start in n time steps. In our tests scenarios, both n = 2 and n = 3 were achievable for a robot. However, depending on the crossing order and time to collision n = 2 sometimes imposed a confidence smaller than Λ.

Depending on the crossing angle and time to collision, the values required for ℒ may not be achievable in practice. For instance, whenever the agent and the robot are sufficiently far away the robot would generate a αnew p,r ≈ 0 no matter the choice of motion change. Moreover, a short time to collision (smaller than one second for instance) would impose limits on the range of motions that can still avoid collision and by consequence limit the range of derivative of bearing angles that can be explored. Given this situation, we choose to focus our approach on situations where time to collision is between one and six seconds. Such mitigation of crossing order mismatch situations is, to our knowledge, novel in the literature where most standard techniques, such as Reciprocal Velocity Obstacles (RVO) and Social Force Model (SFM), assume that crossing order determination is always certain. 97 Chapter 7

Conclusion

"We believe no statistical model is ever final; it is simply a placeholder until a better model is found."

-Judith D. Singer and John B. Willett

This work describes our approach to replicate the manner in which people collaborate to avoid collision while also mitigating potential negative consequences of such collaboration. These results are based on a dataset composed of dyadic collision avoidance situations between people over several crossing angles. This dataset was obtained in a collaboration with the laboratory Mouvement, Sport, Santé (M2S) and it is used to find the manner in which people distribute motion adaptations when avoiding collisions and also to evaluate when people collaborate in an ineffective manner. This chapter summarises our main contributions, and discusses limitations of our current approach as well as possible future work.

Contributions towards human-robot collaboration

In Chapter 5 a model for distribution of effort between a robot and people during collision avoidance was presented. In order to measure effort and its distribution, a cost function, named collision avoidance effort, was developed based on a trade-off between energy spent and time to reach the goal. The distribution of collision avoidance effort between first and last crosser was found to be consistent under repeated initial conditions. Given this consistency, we used Generalized Linear Model (GLM) to estimate the distribution of collision avoidance effort between people. In order to validate our approach, a proof of concept was implemented within Reciprocal Velocity Obstacles (RVO) and compared against standard RVO and also our dataset.

Our other contribution was presented in Chapter 6, where a collision avoidance approach to mitigate the potential negative consequences of collaboration during collision avoidance was described. State of the art works have always assumed that collaboration between agents proceeds without error in the choice of crossing order. In our work, we first developed a metric to confirm that people do not always initially choose distinct crossing orders. Afterwards, we showed that the uncertainty over crossing order can be estimated using the derivative of the bearing angle. Using this estimation, an approach to account for the possibility of both agents choosing the same crossing order and the manner in which one can plan collision avoidance motions to mitigate the negative consequences of such event was presented.

Limitations

Although our simulated experiments are demonstrated with considerable amount of scenarios with distinct initial conditions, the lack of validation with a physical robot in a realworld scenarios is a current limitation of the validation of Chapter 6. Notwithstanding this shortcoming, a recent work has shown that people do behave more naturally when they expect the robot to respect human interaction rules [START_REF] Vassallo | How do walkers behave when crossing the way of a mobile robot that replicates human interaction rules?[END_REF].

Another point is that, in Chapter 6, we assumed that people attempt to resolve nearsymmetry situations while sampling their next derivative of the bearing angle using an uniform distribution. In practice, it would be important to evaluate whether an uniform distribution is sufficient to represent human behavior in near-symmetric scenarios or not.

Among other areas of improvement in our work, we intend to use optimization techniques other than Sequential Least Squares Programming (SLSQP) to compare potential differences in generated collision avoidance velocities. Furthermore, we intend to investigate whether a non-local optimizer would have found better solutions for this particular problem.

Finally, it is also important to evaluate whether the presence of multiple people affect the distribution of motion adaptations in a significant way. Given that our dataset was based in dyadic collision avoidance situations our approach was limited to such cases in order to allow for proper validation. In that context, situations in which avoiding collision with one person increases collision risk with another would be of particular interest.

Perspectives

As our closing remarks we present some perspectives for this work. For short the term:

• Instead of using the uniform distribution to sample values for the derivative of the bearing angle, another possible avenue would be to analyze in the data what is the probability distribution that people use in such situations.

• Generalize the model of collision avoidance under near-symmetry for robot-robot situations in order to account for crossing order error due noise in the determination of position, heading and speed of other agents. This would allow robots that cannot communicate to minimize the time spent in situations of ambiguous crossing order (negotiation phase).

• An interesting future avenue would be to integrate both the shared effort approach and the near symmetry mitigation into the same solution.

For the long-term, perspectives are:

• Running experiments involving more people so that one can highlight how people prioritize effort distribution. In particular, situations where avoiding collision with one person causes collision risk with another person.

• an interesting direction would be to run experiments in a virtual reality environment with one autonomous agent and another agent controlled by a person. In this manner, the risk of physical collision between robot and person would be removed. Moreover, assessing the impact of personal factors, such as cultural norms [START_REF] Chattaraj | Comparison of pedestrian fundamental diagram across cultures[END_REF], can also provide interesting insights.

• Instead of taking reactive decisions, plan over multiple timesteps while accounting for distribution of effort between multiple people, some of which could have an ambiguous crossing order. This opens several novel possibilities where an agent might avoid more efficient collision avoidance motion with one agent in order to avoid entering in an ambiguous crossing order situation with another.

101 mean = acc / n means.append(mean) plt.scatter(Ls, means, color='blue', alpha=0.5, \ zorder=1, label='Mean after 100000 trials') plt.plot(Ls, Ls/3.0, color='black', label='L/3') plt.xlabel("Interval length for uniform distribution") plt.ylabel("Mean distance Y") plt.show()

C.1.2 Confidence in distance larger than threshold

In this section we provide geometric proof that, for a random variable 𝒳 that is uniformly distributed over the interval [0, ℒ], the probability that two points x 1 and x 2 independently sampled from this distribution will be at least κ units away from each other can be calculated using

𝒟 = (ℒ -κ) 2 ℒ 2 (C.4)
where ℒ is the length of the interval.

An uniform random distribution over the interval [0, ℒ] can be represented as a line with a length ℒ where each point is a distinct sample from this distribution. Moreover, the space defined by two samples from this distribution can be similarly represented as a square where each side has a length ℒ. Based on this, we are interested in the combined area of the segment(s) of the square that respect the relation ||x 1 -x 2 ||≥ κ.

For easier visualization, we partition the aforementioned square into two right triangles of equal size using the insight that the distance can be represented as

||x 1 -x 2 ||=    x 1 -x 2 , if x 1 ≤ x 2 x 2 -x 1 if x 2 > x 1 (C.
P(||x 1 -x 2 ||≥ κ) = 2A ℒ 2 = (ℒ -κ) 2 ℒ 2 (C.7)
In the following pages we present our earlier approach towards effort distribution during collision avoidance. This earlier iteration of our approach was not included in the thesis as it was strictly improved upon in [START_REF] Silva | Human inspired effort distribution during collision avoidance in human-robot motion[END_REF] which is described in Chapter 5.

Human Robot Motion: A shared effort approach

Grimaldo Silva 1 and Thierry Fraichard 1Abstract-The traditional approach to Human Robot Motion (HRM) has been to treat the person as a moving obstacle, so that a robot avoids his predicted trajectory. In contrast with such an approach, recent works have showed benefits of human-like motion. One such benefit is that human-like motion was shown to reduce the planning effort for all persons in the environment, given that they tend to solve collision avoidance problems in similar ways. The effort required for avoiding a collision, however, is not shared equally between agents as it varies depending on factors such as visibility and crossing order. Thus, this work tackles HRM using the notion of motion effort and how it should be shared between the robot and the person in order to avoid collisions. To that end our approach learns a robot behavior using Reinforcement Learning that enables it to mutually solve the collision avoidance problem during our simulated trials.

I. Introduction

Human Robot Motion (HRM) is the study of how a robot should move among persons. In this context, robot motion must be safe and appropriate. While safety relates to guaranteeing collision-free motion [START_REF] Fraichard | Inevitable collision states-a step towards safer robots?[END_REF], the term appropriate relates to respecting concepts such as social spaces [2], legibility and perceived safety [START_REF] Lichtenthaler | Influence of legibility on perceived safety in a virtual human-robot path crossing task[END_REF].

Many recent studies have focused on tackling HRM by teaching a robot human-like behavior, such as in [START_REF] Henry | Learning to navigate through crowded environments[END_REF] and [5]. The justification for this approach is that it allows a robot to follow the flow of the persons [START_REF] Henry | Learning to navigate through crowded environments[END_REF], and also allows for better behavior legibility to persons around the robot. Legibility is important because it was shown that humans tend to solve collision avoidance problems in stereotypical ways under repeated conditions [START_REF] Basili | Strategies of locomotor collision avoidance[END_REF], which implies that a robot behaving in an uncommon way forces the person to actively plan its motion instead of relying on already learned stereotypical collision avoidance motion plans, this means that humanlike motion reduces planning effort for all the persons in the environment [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF]. Furthermore, another argument is that unexpected motions can be perceived as unsafe by nearby persons even though in practice they may be collision free [5].

In order to create human-aware robots capable of navigating among persons, most current approaches in HRM, such as [START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF] and [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], operate in two steps. First the probable future behavior of the persons is predicted without considering the robot. Then the future robot motion is computed taking this prediction into account. As a result, the robot always yields, that is, it avoids to the best of its ability regions where a 1 Grimaldo Silva jose.jgrimaldo@gmail.com and Thierry Fraichard thierry.fraichard@inria.fr are with INRIA Rhone-Alpes and University Grenoble Alpes person is expected to go through. Collision avoidance among persons is, however, mutually solved [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF]. This means that, depending on the current disposition of nearby persons, each person is expected to contribute a certain amount of what we call effort to avoid a collision. The amount of effort expected from each person and in which manner this effort is represented, as speed or path changes for example, depends on many factors [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF], [START_REF] Huber | Adjustments of speed and path when avoiding collisions with another pedestrian[END_REF], [START_REF] Jansen | Human locomotion through a multiple obstacle environment: Strategy changes as a result of visual field limthrough[END_REF], such as: who is first, angle of approach, speed and visibility.

In order to replicate human collision avoidance behavior, our approach accounts for two facts: visibility and crossing order. Its important to note, however, that in situations where the person is unwilling or unable to follow a stereotypical motion the robot in our approach will still be able to take full responsibility for avoiding collisions. An important aspect is how the effort needs to be shared between persons and robot. In some situations the person does not expect the robot to yield, such as when the person is behind the robot but intending to overtake. Whereas in other cases the person expects the other agent to give him priority and also to be responsible for most of the collision avoidance [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF], as is the case when the front of the robot would collide into the side of a person during perpendicular crossing scenarios.

Predicting human behavior in reaction to a given robot motion in our approach depends on a human-like model (HLM), which unlike many works in HRM such as [START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF] and [5] does not use the Social Force Model (SFM) which was introduced in [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF]. Instead we rely on a slightly modified version of Optimal Reciprocal Collision Avoidance (ORCA) [START_REF] Van Den Berg | Reciprocal n-Body Collision Avoidance[END_REF], which is also known as RVO 2. This HLM was chosen as it can be directly modified to accommodate different degrees of participation from a particular agent during collision avoidance and easier integration into the robotic frameworks we chose.

Based on the persons' reaction to a given robot motion, we intend to use this information to avoid collisions with persons in a human-like way. To that end, our approach relies on reinforcement learning (RL) [START_REF] Sutton | Reinforcement Learning: An introduction[END_REF] to learn such behaviors, this technique was chosen for its ability to explore the state space and also to learn behaviors that can be recalled even in real-time situations [START_REF] Hester | Texplore: real-time sample-efficient reinforcement learning for robots[END_REF].

A. Outline of the Paper

This work is divided into six sections. Section II describes works with related concepts. Afterwards, in Sec. III a formal description of our approach is presented and also how to measure the additional effort required for collision avoidance. This is followed by Sec. IV where this additional effort measure is used to build a human-like collision avoidance strategy. Experimental results of our approach are presented in Sec. V. Finally, a discussion of our results, future works and final remarks are presented in Sec. VI.

II. Background and Contributions

Initial concepts in HRM focused mainly on allowing a robot to respect social spaces, which can be defined in a general sense as regions that for whatever reason a person considers as belonging to them. Several works attempt to capture the essence of social spaces, among them we highlight: a costmap based approach to personal spaces [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF] and an interaction space among groups of people that was represented using a two-dimensional Gaussian function around groups of people [START_REF] Rios-Martinez | Understanding human interaction for probabilistic autonomous navigation using riskrrt approach[END_REF].

There are many other concepts that have an influence in HRM, such as comfort. Comfort relates to the subjective feeling of a person that the body is relieved of negative stimuli [START_REF] Morales | Including human factors for planning comfortable paths[END_REF]. Many factors affect comfort, one such factor is the visibility which has been tackled in [START_REF] Morales | Including human factors for planning comfortable paths[END_REF] using a multilayer costmap that factors the cost of visibility into a costmap in order to calculate the optimal trajectory of an autonomous wheelchair. A definition of comfortable motion that is more related to HRM was made in [5], can be summarized as the perception of a person being able to walk in their preferred velocity and if their path felt collision free.

Among the several human-like models (HLM) that can approximate human behavior in these cases, we highlight the Extended Social Force Model [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF], a method based on modeling each person as being attracted to their goal (in a preferred velocity) and being repulsed by other agents and also static objects in the environment. Another tool used in simulation of pedestrians, particularly in crowd simulation [START_REF] Narain | Aggregate dynamics for dense crowd simulation[END_REF], [START_REF] Bera | Realtime multilevel crowd tracking using reciprocal velocity obstacles[END_REF], is the reciprocal velocity objects (RVO) [START_REF] Van Den Berg | Reciprocal n-Body Collision Avoidance[END_REF] which is based on finding velocity choices for agents that guarantee collision avoidance.

Given one such HLM, its possible to calculate the reaction of a given person to a robot motion. This contrasts with many current approaches where the planned human motion is static [START_REF] Ferrer | Proactive kinodynamic planning using the extended social force model and human motion prediction in urban environments[END_REF] or probabilistic [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF]. That is, in these works the robot avoids regions where persons are predicted to go in order to avoid disrupting their plans.

Another concept, defined in [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], was hindrance. This term relates to situations where a person natural behavior is disrupted due to a robot's proximity. To that end, a humanlike planner using Markov Decision Process associates a probability for each of the several possible person trajectories to the goal (a distribution over trajectories), this planner is trained by observing human trajectories. Based on this information the robot is able to find a motion to its goal that reduces potential human hindrance by avoiding high hindrance regions.

Our approach brings novel contributions in relation to those works as we focus on learning how to reproduce how persons share collision avoidance. To this end, it is necessary to forecast short-term human motion plan in reaction to a given robot action, which we accomplish with a modified version of ORCA.

III. Overview of the problem

A robot is tasked with reaching a given goal, in-between his current and desired positions any number of persons may cross his path. It is evident that collisions with persons have to be avoided whenever necessary. However, persons have certain expectations about how this collision avoidance should take place. Thus to solve this problem it is important to model how the collision avoidance effort should be distributed.

A. Formalization of the problem

Consider that W represents the environment, with W ⊂ R 2 . This environment is composed of persons, each of these p ∈ D have a positional properties: q p = (x p , y p , θ p ) ∈ R 2 × S 1 . Thus we define the state of a given person as s p = (q p , qp ), where each person also has a goal, which is known a priori, g p = (x * p , y * p , θ * p ) ∈ R 2 × S 1 . Additionally, the robot r is also an agent is this environment and as such also has positional properties s r and a goal g r .

Although human behavior can be the result of large cognitive effort, recent studies showed that realistic trajectories can be generated with simple models where an agent solely avoids local collisions [5]. Thus, our choice to utilize a reactive HLM to evaluate human reaction to a given robot motion over n time steps is reasonable.

One possible approach to the robot-person collision avoidance problem can be posed in terms of minimizing additional human effort. First, let π p,r = {q p (0), . . . , q p (n)} be the predicted trajectory of person p after interaction with a robot r trajectory within a prediction window of n time steps ahead, which represents the necessary number of time steps for the robot to reach the goal for that given trajectory. Moreover, consider that the additional effort of a given trajectory is represented by a function Γ : π p : [0, n] → R * (detailed in Sec. III-B). Finally, consider one possible formulation to this problem

π r * = arg min πr∈Πr p∈P Γ(π p,r ) (1)
where Π r is the set of admissible robot motions to the goal, that is, motions that are safe and also human-like. In this model the robot avoids causing additional effort to the person whenever possible, that is, it will minimize the disruption of the person's motion plan while still reaching its goal. This approach is necessary in case the person is unaware of the robot or either unwilling or incapable of changing his motion plan. Conversely, in real scenarios, a person does not always yield. The additional effort required for collision avoidance is shared between the persons involved. In such context, a robot that acts unlike other persons can generate scenarios where, for example, persons are forced to actively think about the robot motion plan instead of relying on already learned stereotypical trajectories. As such, to achieve HRM it is also necessary for the robot to replicate the ability of persons to share necessary changes in planning between themselves in a socially aware manner in order to solve collision avoidance situations in stereotypical situations.

To account for the effort sharing between person and robot, the problem of collision avoidance is posed as an optimization problem in this manner (2) where α r,p ∈ [0, 1] is the effort distribution coefficient (EDC) between p and r. This coefficient indicates, at each time step, what is the relative cost of the robot's deviation from its baseline goal in relation to the person, a higher proportion engenders less deviation, this is detailed in the section IV.

B. Human trajectory cost function

Anticipating the human effort necessary to execute a given trajectory is a necessary step in order to properly divide effort between person and robot. Many models exist to measure this effort. One such function is the path length and also total time to the goal [START_REF] Lavalle | Planning algorithms[END_REF]. Another approach, is given by [START_REF] Mombaur | From human to humanoid locomotion-an inverse optimal control approach[END_REF], which describes the cost of a trajectory as a combination of weighted acceleration controls.

Our work relies on the concept of understanding how collision avoidance requires additional effort in relation to the robot baseline motion. Baseline motion represents the trajectory that does not account for the presence of other agents in the environment. The interaction with other agents, however, requires change in the motion plan. To measure this change, the first step is calculating the distance of an agent r to the goal at time t using d t (r, g r ) = (x r (t)x * r ) 2 + (y r (t)y * r ) 2 where x r (t) and y r (t) are, respectively, the x and y coordinates of the agent r at time t. Thus, we can define the change in distance to the goal as ∆d r,g = d t (r, g r )-d t-1 (r, g r ). In our approach, at each time step, a baseline change in distance to the goal is estimated, that is, the agent plans its motion without accounting for other agents. This baseline change in distance to the goal at the current time step is represented by ∆B t (r, g) and can be understood as the desired progression to the goal.

However, interaction with other agents require additional effort, which impose changes into the baseline motion of an agent. Given this concept, we can define the additional effort of r for a given trajectory as Γ(π r ) = qr∈πr max{0, ∆d t (r, g r ) -∆B t (r, g r ))}

(3)

This cost function calculates its result based on the difference from the baseline motion to the actual motion. In this formulation, a given motion can only have an equal or smaller cost than the baseline motion at any time step. This definition guarantees that Γ : π p : [0, n] → R * , which is a property that is important in Sec. IV-B, when using it as part of a reward function during optimization.

IV. Presentation of the Approach

Given the initial state of the person and the robot (including position, goal and velocity), the robot wishes to find a trajectory π r * that shares collision avoidance effort among them in a similar way as another person would. Thus, in this section we divide our approach to solve the optimization problem of shared effort presented in Eq. 1 and Eq. 2 in five main steps:

1) Receive information from sensors (world model/state) 2) Find ∀p ∈ D the α r,p based on current state 3) Plan collision avoidance actions up to n steps ahead 4) Send planned velocity (action) to wheels 5) Stop if goal reached, go to step 1 otherwise As the robot receives input from its sensors it builds a representation of the world including position of the goal, position and velocity of nearby persons and also his own. This information can be used to generate what is called a model of its environment -a world model.

Information about position and velocity of nearby persons enables the robot to calculate the amount of effort it should share with each one for human-like collision avoidance. The effort distribution coefficient (EDC) and the steps necessary to calculate it are described in details in Sec. IV-A.

Given the world model and the EDC, the motion plans for future timesteps can be calculated. To that end, RL is used to learn a motion plan capable of reaching a given goal while avoiding collision with a nearby person. Our formulation of this problem as RL problem is described in Sec. IV-B.

Based on this overview of our approach to solve the shared effort collision avoidance problem, in the upcoming subsections the aforementioned steps are detailed and some advantages and limitations of our approach are discussed.

A. Sharing effort

The proportion of effort shared during collision avoidance between person and a robot varies depending on crossing order and crossing angle. It is known that the person that is giving way has to contribute more to the avoidance than the one passing first [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF]. One possible explanation for this comes from difference in visual stimuli that both agents have, as the person that gives way can more easily obtain visual information about the person passing first [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF]. In our current formulation these two factors are taken into account to decide shared effort: crossing order and visibility.

The point of potential collision, which is the position where both agents would collide on in case they continue in their current velocity, forms an angle ζ r,p ∈ [0, 2π] between the current position of the robot r and of person p. Henceforth, when analyzing angles of crossing scenarios, the angle that is being referenced is ζ r,p . Furthermore, the angle β r,p is formed from the bearing-angle of r in relation to the position of p. The derivative of the bearing angle β can be a strong indicator of potential collision and also of crossing order [START_REF] Cutting | How we avoid collisions with stationary and moving obstacles[END_REF]. These angles are shown in Fig. 1.

Based on results found [START_REF] Olivier | Collision avoidance between two walkers: Role-dependent strategies[END_REF] through analysis of the perpendicular crossing scenarios, it was found that the person crossing first has a maximum of 40% contribution in collision avoidance effort, while the one crossing last has a maximum of 40%. Furthermore, it is intuitive that in most situations of head-on collision with similar velocities or when both person and robot see each other but have no clear crossing order, that the effort is shared equally between participants. Conversely, in scenarios where one agent is potentially unaware of the other i.e. the passing agent is coming from behind; the responsibility shifts to the agent that sees the other. Recent results also indicate that agents are still able to avoid collisions even against obstacles in peripheral vision, [START_REF] Marigold | Keep looking ahead? re-direction of visual fixation does not always occur during an unpredictable obstacle avoidance task[END_REF].

This background allows us to correctly distribute effort during collision avoidance between a person and a robot. Thus let α r,p represent the effort sharing coefficient between r in relation to p, which we define as a proportion that weights crossing order and visibility into the relative cost of the robot's deviation from its baseline motion in relation to the person. That is, the higher the proportion, the less deviations from baseline motions of the robot are done in comparison to the person.

The notion that agents do not react to other agents that are outside their field of view, which span around 180 o (with both eyes) when looking ahead [START_REF] Sardegna | The encyclopedia of blindness and vision impairment[END_REF], is translated into our model as a function vv : R → [0, 1]. This model is used for the robot in order to find trajectories that respect humans expectations. Thus, vv is defined as vv(β r,p ) = 0 for |β r,p |≥ π where the constants A, K and λ 2 are, respectively, 0.1, -0.1 and 30. Furthermore, β is the rate of change of β and δ : R → [0, 1] is a function that resembles a smooth approximation of the dirac delta distribution that maps β into 1 -|tanh(λ 3 β)| in which λ 3 = 8 was chosen to appropriately control the rate of convergence from one to zero. The dirac-like distribution was used to guarantee that the effort is always shared evenly during head-on (or near head-on) collision scenarios. Additionally, a generalized logistic function represents the boundary between the head-on collision avoidance case and the perpendicular case (where there may be an unequal distribution of effort).

The function f , showcased in Fig. 2, is not applied in cases where there is no chance of collision, as there is no need to change its motion plan, or in cases where the person does not see the robot. In the latter case, for example, if a robot is trying to pass a person from behind it is not appropriate to expect the person to share effort with the robot as the robot is outside its field of view. Thus, in both cases the robot is responsible for the total motion effort.

B. Human-like collision avoidance

To correctly share effort between a person and a robot the optimization problem defined in Sec. 2 is presented in this section in a way can be solved using Reinforcement Learning [START_REF] Sutton | Reinforcement Learning: An introduction[END_REF]. The most usual way to represent reinforcement learning problems is as a Markov Decision Process (MDP) which defines a tuple containing S, A, R, P that are, respectively, the set of possible states S, the set of possible actions A, the reward function R : S × A × S → R and also a transition function P : S × A → S. At each discrete time step the MDP observes the current state z 0 ∈ S and selects an action a 0 ∈ A, as a result, it reaches a new state z 1 and receives a reward r 1 . Given this formulation, the goal of the MDP is to reach a given terminal state s f with the best expected reward or maximize the expected reward within a certain time frame.

A particular robot behavior, that is, a relation between every state and action is defined as ψ : S → A and called policy. The goal of a reinforcement learning is thus to learn a policy ψ * that provides better reward than any other policy. Among available methods of Reinforcement Learning, TEXPLORE [START_REF] Hester | Texplore: real-time sample-efficient reinforcement learning for robots[END_REF] was selected as our choice as it is robust to noise and able to handle continuous state features.

In order for ψ to make a decision about the future robot motion, the state z t for the robot is as a tuple β r,g , d r,g , ζ r,p , ttc, β r,p , βr,p , d r,p that is used a person where its current motion has risk of collision with the robot, where ttc represents the number of time steps to collision (up to n steps ahead) given linear projection of current velocities, and β is the rate of change of the bearing angle (see Fig. 1).

Using the relative angle and distance to the goal allows the robot to learn what actions better leads him to the goal. For instance, in the absence of collision risk, maintaining the bearing angle of the robot to the goal, β r,g , at near zero guarantees the reward is maximum. In a similar sense β is used to allow the agent to measure the risk of collision, the direction of the collision is given by β r,p and ζ r,p . When collision is detected within the visible range the ttc is set to the predicted amount of time steps, its value is an arbitrary maximum distance of collision detection otherwise.

The possible actions are a discretization of the control space, represented as forward motion and also left and right motions in 45 o angles. The discretization was chosen in such way to reduce learning times. To avoid sharp turns as a result of this discretization, the generated trajectories are smoothed using a B-spline [START_REF] Dierckx | Curve and surface fitting with splines[END_REF]. Given this control space, each action a t in our model can be represented by a control u(t). Furthermore, the motion u(t) can be seen a trajectory of two points and one time step, where its cost can be expressed in terms of Γ, thus for each action a t in state z t its reward is given by r t+1 = -|(1α r,p ) • Γ(u p (t))α r,p • Γ(u r (t))| [START_REF] Carton | Measuring the effectiveness of readability for mobile robot locomotion[END_REF] The reward presented in Eq. 7 is used in case the robot did not reach its goal and there was no collision, in case otherwise, the reward is set to, respectively twenty and minus twenty.

V. Results

In this section we evaluate our approach to shared effort in HRM. The tests were executed inside the ROS framework and its packages. The persons are simulated as holonomic agents using ORCA and are able to change their speed, conversely, the robot has a discretized control space that is always at maximum speed. In these tests, the time step between t and t + 1 of our prediction is equal 0.25 seconds. The robot motion model used is point mass but restricted to three acceptable actions, see section IV-B for further details.

A. Trajectories based on crossing order

The trajectories presented were made accounting for different crossing angles and also with different crossing order expectations in order to evaluate the their feasibility. The goal of the person is a point with a fixed distance away while the goal of the robot is a random position away and an angle near the direction of their heading, this allows one to randomize the crossing order without altering relative velocities. This is so as the person and the robot have approximately the same speed, except in scenarios with crossing order of 180 o , depicted in Fig. 5, where the person has a speed 50% larger than the robot (in order to allow the person to overtake).

It is important to note that there is no perceived order in crossing scenarios with angles of 0 o and 180 o , both depicted in Fig. 5. Whereas in the case of crossing angle 45 o (Fig . 4) and 90 o (Fig. 3) we showcase the different available trajectories in the cases where the robot has the crossing order priority ( βr,p < 0) and in cases where the person has the priority ( βr,p > 0). This work presented an approach to allow a robot to share the effort required to avoid collision with a person by learning a policy that encodes stereotypical behaviors from persons during collision avoidance. The results observed during experimental evaluation show that the robot is capable of sharing effort with angles 0 o , 45 o , 90 o and 180 o without simply yielding to the person.

To our knowledge, this is the first work that approximates the human asymmetrical effort sharing during collision avoidance in 90 o crossing scenarios in different crossing orders. This can allow a robot to better represent human-like behavior, this is important as following stereotypical motions were shown in recent works to reduce planning effort for persons in the environment.

For the short term, our plan is to train and test the system with multiple persons participating into the collision avoidance, where each one has a different velocity. This allows observation of cases where a particular collision avoidance approach may by consequence cause additional effort to somebody else. Moreover, our approach currently makes a best effort to match the effort expectations solely based on the current state of the robot, however, adding a short-term memory of the effort already shared with someone can help balance the effort over multiple time steps. Our long term goal is to apply this model into a real robot that has to avoid collision with multiple persons in a real environment.

1- 1

 1 Robot's perspective in situations of near symmetry. . . . . . . . . . . . . . 2-1 A collision scenario with its corresponding temporal evolution for both distance and Minimum Predicted Distance (MPD) value. . . . . . . . . . . . . 2-2 Breakdown of temporal evolution of MPD over different phases. The MPD values are shown from the start of the interaction until after the end. . . . . 2-3 An example of crossing order being established between people and the same concept in terms of the robot from the perspective of its local coordinate space. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-4 Each unique color represents a distinct homotopy class decision. Paths within the same homotopy class can be continuously deformed into each other. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-1 Different social spaces formed around people. . . . . . . . . . . . . . . . 3-2 The interaction space has to be accounted for during motion planning. Appropriate motion represents more than just guaranteed safe motion. . . . . . 3-3 Robot should account the perception of a person of their behavior. . . . . . 3-4 Treating people as a moving obstacles results in the different joint trajectories 5-1 People collision avoidance behavior being tracked in a square area with twelve meters in length. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-2 Change in the time energy trade-off function in case one walks straight to the goal without obstacles . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-3 Proportion of effort that was done by the person who crosses in front with respect to total effort required to avoid a collision . . . . . . . . . . . . . . 5-4 Collision situation between robot and person, with a given crossing angle, bearing angle and its derivative . . . . . . . . . . . . . . . . . . . . . . . . 5-5 Prediction using Generalized Linear Model (GLM) for collision avoidance effort for person crossing in front and person crossing behind given a range of values for situational factors and three crossing angles. . . . . . . . . . . 5-6 Pipeline to calculate effort distribution from situational factors that are then used as input into Reciprocal Velocity Obstacles (RVO). . . . . . . . . . . 5-7 Three distinct scenarios where changes in effort distribution shifts the majority of effort to avoid collision towards the person crossing behind. . . . . 5-8 Changes in crossing order during collision avoidance can create significant differences in generated trajectories. . . . . . . . . . . . . . . . . . . . . . 5-9 Evaluating manually chosen values of effort distribution in ROS. . . . . . . 5-10 Comparison between collision avoidance trajectories from actual people and simulated robots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-11 Behavior when crossing angle is 180°. Agent in front is three times slower and does not contribute in avoiding the collision. . . . . . . . . . . . . . . 6-1 Human trajectory comparison when crossing order is misjudged. . . . . . . 6-2 Reactive collision avoidance behavior whenever agents incorrectly choose the same crossing order. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-3 Evaluation collision avoidance scenarios between people from our dataset . 6-4 Relationship between the derivative of the bearing angle and the number of decisions for effective collaboration . . . . . . . . . . . . . . . . . . . . . 6-5 Examples of collision avoidance motions with misjudged crossing order. . .

4. 1 15 AcronymsEDC

 115 Comparison between different capabilities in terms of collaboration during collision avoidance in the case of low density situations involving people. . 5.1 Distribution of type of errors during reconstruction of person positions from the dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Expected value of difference in effort distribution of the human trajectories to both Reciprocal Velocity Obstacles (RVO) and our approach. The notation E[•] represents the expected value of a given argument. . . . . . . 6.1 Evaluation of six random variations of two near symmetrical collision scenarios with specific crossing orders. . . . . . . . . . . . . . . . . . . . . . B.1 Link functions and their inverse. . . . . . . . . . . . . . . . . . . . . . . . Effort Distribution Coefficient. 67, 68, 71, 73, 74 ESFM Extended Social Force Model. 47, 49

Figure 1 - 1 :

 11 Figure 1-1: Robot's perspective in situations of near symmetry.

  Temporal evolution of distance and MPD from reconstructed positions.

Figure 2 - 1 :

 21 Figure 2-1: A collision scenario with its corresponding temporal evolution for both distance and MPD value.

Figure 2 - 2 :

 22 Figure 2-2: Breakdown of temporal evolution of MPD over different phases. The MPD values are shown from the start of the interaction until after the end.

  (a) Person crossing in front sees the person crossing behind diverge from the center of its field of view.

  Robot crossing behind sees the other agent converging towards the center of its field of view (local coordinate space).

Figure 2 - 3 :

 23 Figure 2-3: An example of crossing order being established between people and the same concept in terms of the robot from the perspective of its local coordinate space.

  class decisions with respect to a static obstacle.Agent Agent(b) Homotopy class decisions with respect to a moving obstacle.

Figure 2 - 4 :

 24 Figure 2-4: Each unique color represents a distinct homotopy class decision. Paths within the same homotopy class can be continuously deformed into each other.

Contents 3 . 1

 31 Accounting for social spaces during navigation . . . . . . . . . . . . 40 3.1.1 Personal space . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.1.2 Activity, interaction and affordance spaces . . . . . . . . . . . 42 3.2 Approximating internal state of a person . . . . . . . . . . . . . . . 43 3.2.1 The impact on comfort of the presence of a robot . . . . . . . . 43 3.2.2 Legible motion during navigation among people . . . . . . . . 44 3.3 Human-aware collision avoidance . . . . . . . . . . . . . . . . . . . 45 3.3.1 Accounting for the reaction of people to a robot motion . . . . . 46 3.3.2 Robot-person collaboration with joint trajectories . . . . . . . . 47 3.3.3 Following flow of people to avoid collision situations . . . . . . 48 3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

  space formed in a group in conversation.

Figure 3 - 1 :

 31 Figure 3-1: Different social spaces formed around people.

1 .

 1 Public zone > 3.6 meters 2. Social zone > 1.2 meters 3. Personal zone > 0.45 meters 4. Intimate zone ≤ 0.45 meters

Figure 3 - 2 :

 32  The interaction space has to be accounted for during motion planning. Appropriate motion represents more than just guaranteed safe motion. Trajectory in red is safe but not appropriate while trajectory in green is both safe and appropriate.

  (a) Person misunderstands the robot's intention. (b) Person correctly perceives robot's goal.

Figure 3 - 3 :

 33 Figure 3-3: Robot should account the perception of a person of their behavior.

Figure 3 - 4 :

 34 Figure 3-4: Treating the person as either a moving obstacles or as an agent results different joint trajectories. The joint trajectory in blue represents avoidance treating the other as a moving obstacle. In practice, people collaborate during collision avoidance which might yield the joint trajectory in red.

Contents 4 . 1

 41 Collision avoidance collaboration in reactive agents . . . . . . . . . 52 4.1.1 Synthetic vision navigation . . . . . . . . . . . . . . . . . . . . 52 4.1.2 Velocity obstacles and related methods . . . . . . . . . . . . . 53 4.1.3 Social Force Model and related methods . . . . . . . . . . . . . 54 4.2 Planning trajectories for collaborative collision avoidance . . . . . . 55 4.2.1 Learning joint trajectories between agents . . . . . . . . . . . . 55 4.2.2 Kinodynamic planning of trajectories . . . . . . . . . . . . . . 56 4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Figure 5 - 1 :

 51 Figure 5-1: People collision avoidance behavior being tracked in a square area with twelve meters in length and subsequently reconstructed into precise positions over time. The red circle has six meters of diameter and represents the zone of observation where collision avoidance analysis is made. The circle is virtual. This particular future collision has a 150°crossing angle.

Figure 5 - 2 :

 52 Figure 5-2: Change in the time energy trade-off function in accordance to change in timeenergy weight ζ p (v desp ) in case one walks straight to the goal without obstacles. Thus, for each case the minimal value is reached only when the agent arrives at his goal at the desired time using the desired amount of energy. Thus, in case a person accelerates, decelerates or move its heading away from the goal in order to avoid a collision its value will not ever be minimal.

  (a) Probability of a given crossing order doing more effort to avoid a collision (b) Proportion of effort done by the person crossing in front (EDC) with respect to total effort.

Figure 5 - 4 :

 54 Figure 5-4: Collision situation between r and p, where crossing angle φ , bearing angle α front,beh and its derivative αfront,beh are shown. The z is calculated based on bearing and crossing angle. Arrows indicate a velocity vector.

  (a) Person crossing in front (left) and person crossing behind (right). Crossing angle φ = 60°and ttc = 3 secs. (b) Person crossing in front (left) and person crossing behind (right). Crossing angle φ = 90°and ttc = 3 secs. (c) Person crossing in front (left) and person crossing behind (right). Crossing angle φ = 120°and ttc = 3 secs.

Figure 5 - 5 :

 55 Figure 5-5: Prediction using GLM for collision avoidance effort for both roles given a range of values for situational factors and three crossing angles. Effort of the person crossing in front, denoted as Ffront (φ , ∆v, z, ttc), has an upper bound while it grows unbounded for the person crossing behind, denoted by Fbeh (φ , ∆v, z, ttc), as total collision avoidance effort increases. The ∆v is shown in mm/s and z in degrees.

Figure 5 - 6 :

 56 Figure 5-6: Pipeline to calculate effort distribution from situational factors that are then used as input into RVO.

  (a) Effort shared between agents. Both change trajectory. (b) Agent crossing in front does all effort to avoid collision.

Figure 5 - 9 :

 59 Figure 5-9: Evaluating manually chosen values of effort distribution in ROS.

  (a) Collision avoidance with 90°crossing angle. (b) Collision avoidance with 120°crossing angle.

Figure 5 - 10 :

 510  Comparison between collision avoidance trajectories from actual people and simulated robots. Human trajectories are in red, simulated trajectories with our method are in blue.

Figure 5 - 11 :

 511 Figure 5-11: Behavior when crossing angle is 180°. Agent in front is three times slower and does not contribute in avoiding the collision.

Contents 6 . 1

 61 Ambiguous role during collision avoidance between people . . . . . 82 6.1.1 Representing negative impact in collision avoidance progress . . 82 6.1.2 Phases of collision avoidance with ambiguous role . . . . . . . 83 6.2 Boundary in choice of crossing order . . . . . . . . . . . . . . . . . 84 6.2.1 Formalizing the concept of near-symmetry . . . . . . . . . . . 85 6.2.2 Estimating crossing order uncertainty based on data . . . . . . . 86 6.3 Collision avoidance motion for uncertainty mitigation . . . . . . . . 87 6.3.1 Impact of confidence in determination of crossing order . . . . 88 6.3.2 Obtaining a desired confidence with random uniform sampling 88 6.3.3 Generating collision avoidance motion . . . . . . . . . . . . . . 91 6.4 Experimental validation . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.4.1 Impact of linear and angular constraints on motion . . . . . . . 94 6.4.2 Collision avoidance trajectories under near symmetry . . . . . . 96 6.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Figure 6 - 1 :

 61 Figure 6-1: Human trajectory comparison when crossing order is misjudged.

   Reactive collision avoidance approach whenever agents incorrectly choose the same crossing order. Point in red is the collision in case of no change in trajectory. Collision point in orange happens if the agents plan collision avoidance only once. Collision in the blue point when both agents continuously choose to attempt to cross behind. Whenever agents continuously believe they cross in front they reach a stable forward motion without ever colliding with each other or reaching their goal.

Figure 6 - 3 :

 63 Figure 6-3: Evaluation avoidance scenarios between people from out dataset, divided into five partitions. Each partition represents the probability that the predicted homotopy class does not change at any point in the interval [t i ,t f ].

Figure 6 - 4 :

 64  Relationship between the current αr,p (t), the desired number of decisions n to start effective collaboration and ℒ.

  90

  Both attempt to cross in front. Future collision with 90°crossing angle. Constrained by maximum velocity.

  Both attempt to cross behind. Future collision with 90°crossing angle. Less constrained by minimum velocity.

Figure 6 - 5 :

 65 Figure 6-5: Samples of collision avoidance motions with misjudged crossing order. Each color in a dashed line indicates a specific choice of derivative of bearing angle. Solid red and black lines indicate, respectively, initial motion and motion with αr,p .

Figure 6 - 8 :

 68  Several examples of MPDH where agents misjudge crossing order. In the upper plot, the MPDH increased less efficiently during the period where crossing order is misjudged, in the lower plot crossing order being misjudged negatively affected MPDH (its value decreases). Each color represents a distinct collision avoidance situation.

5 )Figure C- 1 :

 51 Figure C-1: Area of interest is the right triangle with two sides of length ℒκ L 2 we obtain the probability

  π r * = arg min πr∈Πr p∈P |(1α r,p ) • Γ(π p,r )α r,p • Γ(π r )|

Fig. 1 :

 1 Fig. 1: Collision situation between the robot r and a person p, where the crossing angle ζ, the bearing angle β and its derivative β are exemplified.

λ 1 is 15 . 6 )Fig. 2 :

 1562 Fig.2: Shared effort space that defines α p,r , both axis in degrees. The value of α r,p indicates the relative cost of the robot's deviation from its baseline motion in relation a person's deviation. In head-on collision, additional effort shared should be equal as there is no crossing order.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Crossing angle of 90 o , where zero indicates the effortaware robot and one the human-like planner

  (a) Three different scenarios where crossing angle is 0 o (b) Three different scenarios where crossing angle is 180 o . The robot does not yield to the simulated person.

Fig. 5 :

 5 Fig. 5: Cases with no crossing order, where zero indicates the effort-aware robot and one the human-like planner

Table 4 .

 4

		Non-human	HA HL Human Effort	Symmetry
		agents			Distribution	Mitigation
	Ondrej et al. 2010 van den Berg et al. 2011 Helbing and Molnár 1995 Kuderer et al. 2012 Ferrer and Sanfeliu 2014b Our approach	•	•	• • • •	• •	•

1: Comparison between different capabilities in terms of collaboration during collision avoidance in the case of low density situations involving people. In this table Human-Aware (HA) indicates that the robot treats people as more than moving obstacles but does not attempt to explicitly imitate characteristics of human collision avoidance. Conversely, Human-like (HL) techniques attempt to replicate certain characteristics of human behavior during collaborative collision avoidance. Finally, (near) symmetry mitigation indicates that the robot accounts for and mitigates the chance that both agents will attempt to incorrectly cross each other on different sides.

Table 5 .

 5 1: Distribution of type of errors from the reconstructed positions of people from the dataset. Error check was done in order, failing in the first step means the second step is not evaluated. The variables t i and t f represent, respectively, the start and end of the collision avoidance in a specific scenario.

	Order	Type of Error

filtered using the concept of MPD (see Chapter 2) to evaluate whether at start of the interaction between agents MPD(t i ) ≥ 1 m. Moreover, to filter out situations with only a trivial amount of motion adaptations between the start and end of the interaction we evaluate whether the relation MPD(t f ) -MPD(t i ) < 0.1 m is true.

Table 5 .

 5 2: Expected value of difference in effort distribution of the human trajectories to both RVO and our approach. The notation E[•] represents the expected value of a given argument.

	055	0.2297 0.2379	0.0083
	0.055 ≤ F(π p ) + F(π r ) < 0.110 0.1990 0.3248 F(π p ) + F(π r ) ≥ 0.110 0.1662 0.3749	0.1258 0.2087

  Evaluation of six random variations of two near symmetrical collision scenarios with specific crossing orders. Positive results, where the value of α-

	Crossing angle Time to collision	αr,p (t i ) n	ℒ	α-r,p -α+ r,p
	30°2.89s	1.40°3 0.06°3.00°3
	0°2.53s	0.47°3 3.15°2.50°3
	0°2.47s	1.03°3 1.48°2.50°3
	0°2.11s	0.75°3 2.38°3.00°3
	0°2.05s	2.22°3 0.00°1.25°3
	0°1.64s	1.13°3 1.13°0.50°1
	20°2.58s	1.20°2 6.95°7.50°1
	20°2.52s	0.77°2 7.96°7.25°1
	20°2.51s	10.09°2 0.00°10.75°1
	20°2.17s	9.01°2 0.00°11.25°1
	20°1.75s	2.65°2 2.33°8.00°1
	20°1.69s	1.64°2 5.77°6.00°T
	able 6.1:

Scientific contributions described in this thesis include:

The concept of personal space is described in details in Chapter 3.

For more information on total derivatives see[START_REF] Wolfram | [END_REF]

The equations to deal with multiple agents were not included in order to simplify demonstration.

Homotopy class decisions are referred as topological variants in[START_REF] Kuderer | Feature-based prediction of trajectories for socially compliant navigation[END_REF].

In terms of homotopy class, as discussed in Sec.

2.3, choosing the same roles means choosing different homotopy class decisions -an ineffective collaboration choice.

Do note that although αr,p (t) = αp,r (t), the values of αnew r,p and αnew p,r are not necessarily equal as in this case we are evaluating the new velocity of one agent against the current velocity of the other agent (and vice-versa).

Acknowledgments

ACKNOWLEDGMENT This work is supported by the Brazilian National Counsel of Technological and Scientific Development (CNPq).

Appendix A: List of publications

A list of the publications associated with this work is shown within this appendix. Moreover, their respective references are also displayed alongside an overview of the contributions within each publication.

Appendix B: Generalized Linear Model

An introduction to Generalized Linear Model is made which is followed by a theoretical description of its characteristics and components. Moreover, a presentation of the most commonly used distributions and link functions are also presented. The concept of GLM is Appendix C: Properties of Uniform Distributions A short theoretical introduction to uniform distributions is showcased in this appendix. Presenting the notation of density and cumulative distribution functions of uniform distributions. Furthermore, a discussion about two properties of uniform distribution is made and the manner in which these properties can be applied into Chapter 6 in order to mitigate the negative impact of near-symmetry in a collision avoidance scenario is discussed. Appendix A

Human behavior

List of publications

The results described in this thesis have appeared in the following scientific papers

• Human Robot Motion: A shared effort approach [START_REF] Silva | Human robot motion: A shared effort approach[END_REF]. This work also attempted to follow a more human-like distribution of motion adaptations between agents that are avoiding collision with each other. As collision avoidance strategy, Reinforcement Learning was used as a proof of concept. The results found that, while the run-time performance was acceptable actual human data was necessary to validate and improve the results.

• Human inspired effort distribution during collision avoidance in human-robot motion [START_REF] Silva | Human inspired effort distribution during collision avoidance in human-robot motion[END_REF]. This is our first work based on empirical data obtained in a cooperation with another laboratory. This work establishes the effort distribution between people based on situational factors that describe a given collision scenario.

The results pointed towards an upper bound in the amount of effort to avoid collision invested by the person crossing in front while the effort of the person crossing behind grows unbounded.

• Effective Human-Robot Collaboration in near symmetry collision scenarios in [START_REF] Silva | Effective Human-Robot Collaboration in near symmetry collision scenarios[END_REF]. This work focuses on the potential negative side effect of collaboration. We examine so-called (near) symmetric scenarios of collision avoidance where the crossing order decision of each agent is ambiguous. In such scenarios, the robot and the person may incorrectly choose the same crossing order. Our navigation approach then understands the underlying causes of this ambiguity and plans collision avoidance in such a way that even if at first agents choose the same crossing order, they would be able to perceive the correct crossing order in their next decision step.

103

Appendix B

Generalized Linear Model

Linear regression models assume constant variance in their data [START_REF] Dunn | Generalized linear models with examples in R[END_REF].

In contrast, a Generalized Linear Model (GLM) assume that the response to a set of explanatory variables (or predictors) comes from a distribution other than a normal distribution. In practice, this allows a GLM to unify various other statistical models such as linear regression and Poisson regression [START_REF] Nelder | Generalized linear models[END_REF].

A GLM is composed of three main components:

• A random component of a model, represented by a probability distribution of the response variable given the values of the explanatory variables (predictors).

• The explanatory variables (X 1 , X 2 , ..., X k ) and their linear combination η = β 0 +

• A relationship between explanatory variables and the mean response values -a link function

In GLM each response is assumed to be generated from a distribution of the exponential dispersion model family [START_REF] Madsen | Introduction to general and generalized linear models[END_REF]. The mean µ of this distribution depends on the exploratory variables and is calculated as:

where g is the link function and g -1 its inverse. The weights β (unknown parameters) are estimated using maximum likelihood.

Distribution

Canonical link Link function Inverse link function

Normal Identity

Table B.1: Link functions and their inverse.

B.1 Distributions and Link functions

Distributions from the exponential dispersion model family can be categorized into discrete and continuous. Example of discrete distributions are Poisson and binomial while continuous examples are normal and gamma distributions.

The relationship between linear combination of the explanatory variables and the mean of the chosen distribution function is given by the link function. This function g(•) is monotonic, differentiable and relates the values of µ to the values of the linear predictor η [START_REF] Dunn | Generalized linear models with examples in R[END_REF].

For each distribution, a canonical link function is defined based on the exponential of the density function of the response.

In Table B.1, some of the most common distributions and their canonical link functions are presented. The choice of distribution and their canonical link function are generally chosen based on the problem to be modeled. For instance, binomial distributions with logit link functions are generally used to count positive and negative occurrences of a given event.

Appendix C Properties of uniform distributions

A symmetric distribution where each event has the same probability is called a uniform or rectangular distribution.

A uniform distribution can be characterized using two parameters, denoted as a and b with -∞ < a < b < ∞, representing its minimum and maximum value respectively. An uniform distribution can be thus abbreviated as

The probability density function of a uniform distribution is given by

and its cumulative distribution function

C.1 Distance between sampled elements from uniform distribution

In Chapter 6, it was necessary to have a certain confidence that the distance between two points sampled from the same uniform distribution is larger than a given threshold κ. In order to obtain such confidence, it is necessary to control the interval length of the uniform distribution. To that end, two strategies were considered:

C.1.1 Average distance between samples

In this section we provide a justification 1 of why given two random variables 𝒳 1 and 𝒳 2 that are uniformly distributed over the interval [0, ℒ], represented as 𝒰(0, ℒ), have a distance

in average. Suppose that given X 1 and X 2 we also choose a third random variable 𝒳 3 , also uniformly sampled from an interval of length ℒ. The value of 𝒳 3 will be between 𝒳 1 and 𝒳 2 , in average, 1/3 of the time as they are equiprobable. This means that the distance between 𝒳 1 and 𝒳 2 needs to be, in average, a third of the length of the interval and as such can be calculated simply as E[Y ] = ℒ 3 . Empirical verification provided provided below.