A simulação do movimento de humanos virtuais em mundos sintéticos é necessária a áreas tais como: jogos eletrônicos, filmes, ambientes virtuais colaborativos como Second Life R , simulação de pedestres, sistemas de treinamento e simulação de evacuações em situações de emergência. Contudo, mesmo sendo um importante tópico de pesquisa desde a década de 70, a simulação de comportamentos para personagens virtuais ainda é um desafio. O principal objetivo deste trabalho é estender a técnica proposta por Dapper et al. (DAPPER, 2007) onde foi apresentado um planejador de movimento para humanos virtuais que fornece trajetórias suaves e dependentes de parâmetros individuais dos agentes, permitindo a navegação de grupos de forma mais eficiente. Neste trabalho, é proposto um algoritmo para controlar o movimento de grupos em ambientes interativos e uma estratégia para manter a formação durante o deslocamento. O método é baseado em campos potenciais, ou seja, na solução numérica de problemas de valores de contorno envolvendo a equação de Laplace. O método proposto, é composto de duas camadas. Na primeira camada, um mapa para o controle do grupo é criado para possibilitar o controle de cada indivíduo, enquanto que na segunda camada, um algoritmo de planejamento de caminho é utilizado para o movimento do grupo como um todo. A técnica proposta combina o planejamento de movimento para grupos com a navegação baseada em esboços. Os resultados mostram que a técnica é robusta e pode ser utilizada em tempo-real. / The motion simulation of the movement of virtual humans in synthetic worlds is necessary for areas such as: electronic games, movies, collaborative virtual environments such as Second Life R , pedestrian simulation, training systems, simulation of evacuations in emergency situations. However, although being an important research topic since the 70s, the simulation of behaviors for virtual characters is still a challenge. Dapper et al. (DAPPER, 2007) developed a motion planner that provides smooth trajectories dependent on the individual parameters of the agents. The main goal of this work is to extend the technique proposed by Dapper, allowing for a more efficient control and navigation of groups. In this work, an algorithm for the control of group motion in interactive environments is proposed, along with a strategy for maintaining the group formation during the motion. The method is based on potential fields, more specifically, on the numeric solution of boundary-value problems involving the Laplace equation. The proposed method has two layers. In the first layer, a map for group control is created in order to allow for the control of every individual, while in the second layer a path planning algorithm is used for the movement of the group as a whole. The proposed technique combines the planning of group movements with a sketch-based navigation. The results show that the technique is robust and can be used in real-time.

A simulação do movimento de humanos virtuais em mundos sintéticos é necessária a áreas tais como: jogos eletrônicos, filmes, ambientes virtuais colaborativos como Second Life R , simulação de pedestres, sistemas de treinamento e simulação de evacuações em situações de emergência. Contudo, mesmo sendo um importante tópico de pesquisa desde a década de 70, a simulação de comportamentos para personagens virtuais ainda é um desafio. O principal objetivo deste trabalho é estender a técnica proposta por Dapper et al. (DAPPER, 2007) onde foi apresentado um planejador de movimento para humanos virtuais que fornece trajetórias suaves e dependentes de parâmetros individuais dos agentes, permitindo a navegação de grupos de forma mais eficiente. Neste trabalho, é proposto um algoritmo para controlar o movimento de grupos em ambientes interativos e uma estratégia para manter a formação durante o deslocamento. O método é baseado em campos potenciais, ou seja, na solução numérica de problemas de valores de contorno envolvendo a equação de Laplace. O método proposto, é composto de duas camadas. Na primeira camada, um mapa para o controle do grupo é criado para possibilitar o controle de cada indivíduo, enquanto que na segunda camada, um algoritmo de planejamento de caminho é utilizado para o movimento do grupo como um todo. A técnica proposta combina o planejamento de movimento para grupos com a navegação baseada em esboços. Os resultados mostram que a técnica é robusta e pode ser utilizada em tempo-real. / The motion simulation of the movement of virtual humans in synthetic worlds is necessary for areas such as: electronic games, movies, collaborative virtual environments such as Second Life R , pedestrian simulation, training systems, simulation of evacuations in emergency situations. However, although being an important research topic since the 70s, the simulation of behaviors for virtual characters is still a challenge. Dapper et al. (DAPPER, 2007) developed a motion planner that provides smooth trajectories dependent on the individual parameters of the agents. The main goal of this work is to extend the technique proposed by Dapper, allowing for a more efficient control and navigation of groups. In this work, an algorithm for the control of group motion in interactive environments is proposed, along with a strategy for maintaining the group formation during the motion. The method is based on potential fields, more specifically, on the numeric solution of boundary-value problems involving the Laplace equation. The proposed method has two layers. In the first layer, a map for group control is created in order to allow for the control of every individual, while in the second layer a path planning algorithm is used for the movement of the group as a whole. The proposed technique combines the planning of group movements with a sketch-based navigation. The results show that the technique is robust and can be used in real-time.

Ce document explore l'utilisation de méthodes de planification automatique dans des simulations interactives. Lors de simulations de montage et de démontage de composants industriels en environnement virtuel, l'utilisateur peut nécessiter une assistance. Cette assistance est réalisée par l'utilisation d'une solution de planification de trajectoire en temps réel. Cette solution permet la construction interactive d'une chemin par la combinaison de l'avis de l'utilisateur avec la performance de planificateurs automatiques. / This PhD thesis explores the use of motion planning methods in interactive simulations. In the context of assembling and disassembling simulations of industrial components using haptic devices, the user may require assistance to find collision free paths. This assistance can be provided using real time interactive path planning methods. Our solution allows an interactive construction of free paths by combining the opinion of the user with the performance of fast modified automatic path planners.

<p>The problem with motorized wheelchairs is that they are large, clumsy and difficult to control. This is especially true if the driver has severely reduced capabilities. What we want is a wheelchair that can take instructionsfrom the driver and then based on its understanding of the environment, construct a plan that will take the user to the intended destination. The user should be able to sit in a room, tell the wheelchair that he wants to be in another room and the wheelchair should take him there as quickly and smoothly as possible. </p><p>The planner presented in this thesis uses a randomized bi-directional tree search. It builds two trees, one from the start state and one from the goal state by randomly sampling the control space of the robot. Each node is a state and each edge is a control input to the robot.</p><p>In order to decrease the execution time and improve path quality, the planner uses several heuristics to guide the planner. The heuristics are based on Rapidly-exploring Random Trees, Probabilistic Road-maps and the gradient method. </p><p>For a normal household situation, this planner can construct a decent plan in mere seconds on relatively slow hardware. Most times it finishes in a fraction of a second. </p><p>This means that the planner has the ability to run in real-time. As a consequence, the planner can handle a dynamic environment, inaccurate sensor readings and an inaccurate physical robot model.</p>

We consider the problem of moving a three dimensional solid object among polyhedral obstacles. The traditional formulation of configuration space for this problem uses three translational parameters and three angles (typically Euler angles), and the constraints between the object and obstacles involve transcendental functions. We show that a quaternion representation of rotation yields constraints which are purely algebraic in a higher-dimensional space. By simple manipulation, the constraints may be projected down into a six dimensional space with no increase in complexity. Using this formulation, we derive an efficient exact intersection test for an object which is translating and rotating among obstacles.

This report presents a system for generating a stable, feasible, and reachable grasp of a polyhedral object. A set of contact points on the object is found that can result in a stable grasp; a feasible grasp is found in which the robot contacts the object at those contact points; and a path is constructed from the initial configuration of the robot to the stable, feasible final grasp configuration. The algorithm described in the report is designed for the Salisbury hand mounted on a Puma 560 arm, but a similar approach could be used to develop grasping systems for other robots.

This thesis presents a new high level robot programming system. The programming system can be used to construct strategies consisting of compliant motions, in which a moving robot slides along obstacles in its environment. The programming system is referred to as high level because the user is spared of many robot-level details, such as the specification of conditional tests, motion termination conditions, and compliance parameters. Instead, the user specifies task-level information, including a geometric model of the robot and its environment. The user may also have to specify some suggested motions. There are two main system components. The first component is an interactive teaching system which accepts motion commands from a user and attempts to build a compliant motion strategy using the specified motions as building blocks. The second component is an autonomous compliant motion planner, which is intended to spare the user from dealing with "simple" problems. The planner simplifies the representation of the environment by decomposing the configuration space of the robot into a finite state space, whose states are vertices, edges, faces, and combinations thereof. States are inked to each other by arcs, which represent reliable compliant motions. Using best first search, states are expanded until a strategy is found from the start state to a global state. This component represents one of the first implemented compliant motion planners. The programming system has been implemented on a Symbolics 3600 computer, and tested on several examples. One of the resulting compliant motion strategies was successfully executed on an IBM 7565 robot manipulator.

Mobile robots have found numerous applications in recent years, in areas such as consumer robotics, environmental monitoring, security and transportation. For information dissemination, multi-robot cooperation or operator intervention, reliable communications are important. The combination of communication constraints with other requirements in robotics, such as navigation and obstacle avoidance is called communication-aware motion planning. To facilitate integration, communication-aware methods should fit into traditional layered architectures of motion planning. This thesis contains two main contributions, applicable to such an architecture. The first contribution is to develop strategies for exploiting multipath fading while following a reference trajectory. By deviating from the reference, a robot can stop and communicate at positions with high signal strength, trading tracking performance for link quality. We formulate this problem in three different ways: First we maximize the link quality, subject to deterministic bounds on the tracking error. We control the velocity based on the position and channel quality. Second, we consider probabilistic tracking error bounds and develop a cascaded control architecture that performs time-triggered stopping while regulating the tracking error. Third, we formulate a hybrid optimal control problem, switching between standing still to communicate and driving to improve tracking. The resulting channel quality is analyzed and we perform extensive experiments to validate the communication model and compare the proposed methods to the nominal case of driving at constant velocity. The results show good agreement with the model and improvements of over 100% in the throughput when the channel quality is low. The second contribution is to plan velocities for a group of N robots, moving along pre-determined paths through an obstacle field. Robots can only communicate if they have an unobstructed line of sight, and the problem is to maintain connectivity while traversing the paths. This is mapped to motion planning in an N-dimensional configuration space. We propose and investigate two solutions, using a rapidly exploring random tree (RRT) and an exact method inspired by cell decomposition. The RRT method scales better with the problem size than the exact method, which has a worst-case time complexity that is exponential in the number of obstacles. But the randomization in the RRT method makes it difficult to set a timeout for the solver, which runs forever if a problem instance is unsolvable. The exact method, on the other hand, detects unsolvable problem instances in finite time. The thesis demonstrates, both in theory and experiments, that mobile robots can improve communications by planning trajectories that maintain visual connectivity, or by exploiting multipath fading when there is no line of sight. The proposed methods are well suited for integration in a layered motion planning architecture. / QC 20120117

Simulating large numbers of agents, performing complex behaviors in realistic environments is a difficult problem with applications in robotics, computer graphics and animation. A multi-agent system can be a useful tool for studying a range of situations in simulation in order to plan and train for actual events. Systems supporting such simulations can be used to study and train for emergency or disaster scenarios including search and rescue, civilian crowd control, evacuation of a building, and many other training situations. This work describes our approach to multi-agent systems which integrates a roadmap-based approach with agent-based systems for groups of agents performing a wide range of behaviors. The system that we have developed is highly customizable and allows us to study a variety of behaviors and scenarios. The system is tunable in the kinds of agents that can exist and parameters that describe the agents. The agents can have any number of behaviors which dictate how they react throughout a simulation. Aspects that are unique to our approach to multi-agent group behavior are the environmental encoding that the agents use when navigating and the extensive usage of the roadmap in our behavioral framework. Our roadmap-based approach can be utilized to encode both basic and very complex environments which include multi- level buildings, terrains and stadiums. In this work, we develop techniques to improve the simulation of multi-agent systems. The movement strategies we have developed can be used to validate agent movement in a simulated environment and evaluate building designs by varying portions of the environment to see the effect on pedestrian flow. The strategies we develop for searching and tracking improve the ability of agents within our roadmap-based framework to clear areas and track agents in realistic environments. The application focus of this work is on pursuit-evasion and evacuation planning. In pursuit-evasion, one group of agents, the pursuers, attempts to find and capture another set of agents, the evaders. The evaders have a goal of avoiding the pursuers. In evacuation planning, the evacuating agents attempt to find valid paths through potentially complex environments to a safe goal location determined by their environmental knowledge. Another group of agents, the directors may attempt to guide the evacuating agents. These applications require the behaviors created to be tunable to a range of scenarios so they can reflect real-world reactions by agents. They also potentially require interaction and coordination between agents in order to improve the realism of the scenario being studied. These applications illustrate the scalability of our system in terms of the number of agents that can be supported, the kinds of realistic environments that can be handled, and behaviors that can be simulated.

This thesis considers the problem of a robot with complex dynamics navigating a partially discovered environment to satisfy a temporal logic formula consisting of both a co-safety formula component and a safety formula component. We employ a multi-layered synergistic framework for planning motions to satisfy a temporal logic formula, and we combine with it an iterative replanning strategy to locally patch the robot's discretized internal representation of the workspace whenever a new obstacle is discovered. Furthermore, we introduce a notion of ``closeness'' of satisfaction of a linear temporal logic formula, defined by a metric over the states of the corresponding automaton. We employ this measure to maximize partial satisfaction of the co-safety component of the temporal logic formula when obstacles render it unsatisfiable. For the safety component of the specification, we do not allow partial satisfaction. This introduces a general division between ``soft'' and ``hard'' constraints in the temporal logic specification, a concept we illustrate in our discussion of future work. The novel contributions of this thesis include (1) the iterative replanning strategy, (2) the support for safety formulas in the temporal logic specification, (3) the method to locally patch the discretized workspace representation, and (4) support for partial satisfaction of unsatisfiable co-safety formulas. As our experimental results show, these methods allow us to quickly compute motion plans for robots with complex dynamics to satisfy rich temporal logic formulas in partially unknown environments.