# Collision Avoidance from Multiple Passive Agents with Partially Predictable Behavior
## 1 Introduction  
Motion planning in dynamic environments has become central to the operations of robots. Most modern applications require navigation of robots among humans, vehicles and other robots. Almost all of the mobile robots in the real world applications are subjected to kinodynamic constraints like differential driven or car-like robots [1; 2]. Many different kinds of motion planning algorithms have been developed for such robots facing static environment, and then they were further extended for dynamic environments. In [3], a motion planning approach for the car-like robots was presented, and it was proved that the path for holonomic robots lying in an open configuration space could be transformed into an equally useful path for nonholonomic robots. Particularly, an algorithm was proposed to generate a useful path for nonholonomic systems based on the path obtained for holonomic robots. However, that transformation was not smooth for car-like robots. It was first proposed in [4] and their idea was further improved in [5]. However, instead of using a steering function, authors presented a method based on computing clothoid curves. Although their methodimproved transition and smoothness, authors did not address complete trajectory planning for dynamic environments. For this propose many authors have proposed different algorithms focusing on complete trajectory planning, such as [6; 7; 8]. In some of these works, the problem of robot motion planning in a dynamic environment was decomposed into hatching an achievable path for nonholonomic systems, and designing a velocity profile by which such vehicles could maneuver safely [9; 10; 11]. However, these approaches do not perform well for navigating a robot in a dynamic environment with multiple moving agents, like pedestrian environment, due to following reasons. (1) These approaches do not take into account the future prediction of obstacle motion thus robot being blinded to a potential collision. (2) When planning in such dynamic environment the time available to compute solution is limited, it is the function of nature and dynamicity of the environment. Therefore, in a highly dynamic environment there is a high probability that a complete path to the goal cannot be computed in the available time. In [12; 13], the problem of kinodynamic motion planning for a robot in a dynamic environment was addressed. The proposed approaches explore the state-time space of the robot to find a collision free path to the goal, while it was assumed that the entire path of the passive agents is known. However, this assumption restricts their application when extending them to pedestrian or multi-agent environment. In most of the applications of navigating an agent, the moving obstacles has free will, and their future behavior is only partially predictable (if at all). When facing such situation, obstacle's path must be predicted using prediction techniques such as the ones presented in [14; 15; 16; 17]. When the on-line path prediction is used to plan motion, it is likely that the model of the future that is obtained will have limited time duration. In addition, such on-line prediction is noisy. Therefore, a planner is required that takes into account the validity duration of the model of the environment and allowable time for computing a solution. Also, it is necessary to consider various sources of uncertainties present, e.g., passive agents unpredictability, uncertainty in resulting state under a given control action, and localization error. Some of the principal work that considers the future behavior of pedestrians or other kind of agents is focused on the concept of velocity obstacle (VO) [18]. The original formulation of VO was designed for an agent with simple-agent dynamics to avoid a collision with a passive agent moving along a known straight path. In [19], authors proposed an optimal reciprocal collision avoidance strategy (ORCA) for multiple active agents, considering similar behavior for all agents.