We study the sparsity and optimality properties of crowd navigation and find that existing techniques do not satisfy both criteria simultaneously: either they achieve optimality with a prohibitive number of samples or tractability assumptions make them fragile to catastrophe. For example, if the human and robot are modeled independently, then tractability is attained but the planner is prone to overcautious or overaggressive behavior. For sampling based motion planning of joint human-robot cost functions, for @math agents and @math step lookahead, @math samples are needed for coverage of the action space. Advanced approaches statically partition the action space into free-space and then sample in those convex regions. However, if the human is into free-space, then the partition is misleading and sampling is unsafe: free space will soon be occupied. We diagnose the cause of these deficiencies---optimization happens over space---and propose a novel solution: optimize over trajectory space by using a Gaussian process (GP) basis. We exploit the "kernel trick" of GPs, where a continuum of trajectories are captured with a mean and covariance function. By using the mean and covariance as proxies for a trajectory family we reason about collective trajectory behavior without resorting to sampling. The GP basis is sparse and optimal with respect to collision avoidance and robot and crowd intention and flexibility. GP sparsity leans heavily on the insight that joint action space decomposes into free regions; however, the decomposition contains feasible solutions only if the partition is dynamically generated. We call our approach .
@cite_61: 
@cite_18: 
@cite_67: 
@cite_15: The paper presents a navigation algorithm for dynamic probabilistic environments. The static environment is unknown; moving pedestrians are detected and tracked on-line. Pedestrians are supposed to move along typical motion patterns represented by HMMs. The planning algorithm is based on an extension of the Rapidly-exploring Random Tree algorithm, where the likelihood of the obstacles future trajectory and the probability of collision is explicitly taken into account. The algorithm is used in a partial motion planner, and the probability of collision is updated in real-time according to the most recent estimation. Results show the performance for a car-like robot in a simulated environment among multiple dynamic obstacles.
@cite_28: 
@cite_36: This paper proposes a navigation algorithm that considers the states of humans and robots in order to achieve harmonious coexistence between them. A robot navigation in the presence of humans and other robots is rarely considered in the field of robotics. When navigating through a space filled with humans and robots with different functions, a robot should not only pay attention to obstacle avoidance and goal seeking, it should also take into account whether it interferes with other people or robots. To deal with this problem, we propose several harmonious rules, which guarantee a safe and smooth navigation in a human-robot environment. Based on these rules, a practical navigation method-human-centered sensitive navigation (HCSN)-is proposed. HCSN considers the fact that both humans and robots have sensitive zones, depending on their security regions or on a human's psychological state. We model these zones as various sensitive fields with priorities, whereby robots tend to yield socially acceptable movements.
@cite_9: Based on a rigorous mathematical analysis, the authors present a systematic overview and a critical discussion of the inherent problems of potential field methods (PFMs). The authors previously (1989) developed a PFM called the virtual force field (VFF) method. Much insight has been gained into the strengths and weaknesses of this method. Four distinct drawbacks with PFMs are identified. Because of these drawbacks, the authors abandoned potential field methods and developed a new method for fast obstacle avoidance. This method, called the vector field histogram method, produces smooth, nonoscillatory motion, while sampling time and hardware are identical to those used in the VFF method. >
@cite_48: For its own safety, a robot system should never find itself in a state where there is no feasible trajectory to avoid collision with an obstacle. Such a state is an Inevitable Collision State (ICS). The ICS concept is particularly useful for navigation in dynamic environments because it takes into account the future behaviour of the moving objects. Accordingly it requires a model of the future evolution of the environment. In the real-world, the future trajectories of the obstacles are generally unknown and only estimates are available. This paper introduces a probabilistic formulation of the ICS concept which incorporates uncertainty in the model of the future trajectories of the obstacles. It also presents two novel probabilistic ICS-checking algorithms that are compared with their deterministic counterpart.
@cite_54: Motion safety for robotic systems operating in the real world is critical (especially when their size and dynamics make them potentially harmful for themselves or their environment). Motion safety is a taken-for-granted and ill-defined notion in the Robotics literature and the primary contribution of this paper is to propose three safety criteria that helps in understanding a number of key aspects related to the motion safety issue. A number of navigation schemes used by robotic systems operating in the real-world are then evaluated with respect to these safety criteria. It is established that, in all cases, they violate one or several of them. Accordingly, motion safety, especially in the presence of moving objects, cannot be guaranteed (in the sense that these robotic systems may end up in a situation where a collision inevitably occurs later in the future). Finally, it is shown that the concept of inevitable collision states introduced by Fraichard and Asama (2004) does respect the three above-mentioned safety criteria and therefore offers a theoretical answer to the motion safety issue.
@cite_27: We present a user study and dataset designed and collected to analyze how humans use space in face-to-face interactions. In a proof-of-concept investigation into human spatial dynamics, a Hidden Markov Model (HMM) was trained over a subset of features to recognize each of three interaction cues - initiation, acceptance, and termination - in both dyadic and triadic scenarios; these cues are useful in predicting transitions into, during, and out of multi-party social encounters. It is shown that the HMM approach performed twice as well as a weighted random classifier, supporting the feasibility of recognizing and predicting social behavior based on spatial features.
@cite_23: This paper presents a trajectory planning algorithm for a robot operating in dynamic human environments. Environments such as pedestrian streets, hospital corridors, train stations or airports. We formulate the problem as planning a minimal cost trajectory through a potential field, defined from the perceived position and motion of persons in the environment.
@cite_49: We present a novel approach for determining robot movements that efficiently accomplish the robot's tasks while not hindering the movements of people within the environment. Our approach models the goal-directed trajectories of pedestrians using maximum entropy inverse optimal control. The advantage of this modeling approach is the generality of its learned cost function to changes in the environment and to entirely different environments. We employ the predictions of this model of pedestrian trajectories in a novel incremental planner and quantitatively show the improvement in hindrance-sensitive robot trajectory planning provided by our approach.
@cite_47: Due to the anticipated future, extensive use of robots, human beings will probably share common spaces with them. The relationships between robots and humans will be conducted at close distances. Predicting people's future positions helps robots understand human behavior and react safely and naturally. In this paper, we propose a method for predicting people's positions in crossing behaviors, i.e. different trajectories people follow when they are crossing each other. We conducted a field experiment to gather various crossing behaviors of pedestrians in a shopping mall environment and analyzed them by focusing on “hot areas” spaces where people modify their trajectories for crossing. We clustered typical crossing behaviors in hot areas and modeled them using Hidden Markov Models for predictions. Our algorithm more accurately predicts the future positions of pedestrians by considering moving direction and speed.
@cite_34: As robots enter the everyday physical world of people, it is important that they abide by society's unspoken social rules such as respecting people's personal spaces. In this paper, we explore issues related to human personal space around robots, beginning with a review of the existing literature in human-robot interaction regarding the dimensions of people, robots, and contexts that influence human-robot interactions. We then present several research hypotheses which we tested in a controlled experiment (N=30). Using a 2 (robotics experience vs. none: between-participants) × 2 (robot head oriented toward a participant's face vs. legs: within-participants) mixed design experiment, we explored the factors that influence proxemic behavior around robots in several situations: (1) people approaching a robot, (2) people being approached by an autonomously moving robot, and (3) people being approached by a teleoperated robot. We found that personal experience with pets and robots decreases a person's personal space around robots. In addition, when the robot's head is oriented toward the person's face, it increases the minimum comfortable distance for women, but decreases the minimum comfortable distance for men. We also found that the personality trait of agreeableness decreases personal spaces when people approach robots, while the personality trait of neuroticism and having negative attitudes toward robots increase personal spaces when robots approach people. These results have implications for both human-robot interaction theory and design.
Proxemics @cite_18 studies proximity relationships, providing insight about social robot design: in @cite_27 @cite_28 @cite_34 proxemics informs navigation protocol. Similarly, @cite_47 studies pedestrian crossing behaviors using proxemics. @cite_23 RRTs are combined with a proxemic potential field @cite_9 . Instead of using proxemic rules, @cite_67 adopts the criteria of @cite_36 . Personal space rules guide the robot's behavior by extending the Risk-RRT algorithm developed in @cite_15 (Risk-RRT extends RRT to include the probability of collision along candidate trajectories). The work in @cite_61 is more agnostic about cultural considerations; a probabilistic collision cost'' is based on @cite_48 . The work in @cite_54 argues that robot and environment dynamics and a sufficient look-ahead guarantees collision avoidance. Although these approaches model human-robot interaction, they do not model human-robot : respecting a proper distance between human and robot (similar to @cite_49 ) is emphasized.