Control of complex systems satisfying rich temporal specification has become an increasingly important research area in fields such as robotics, control, automotive, and manufacturing. Popular specification languages include temporal logics, such as Linear Temporal Logic (LTL) and Computational Tree Logic (CTL), which extend propositional logic to capture the temporal sequencing of system properties. The focus of this dissertation is on the control of high-dimensional systems and on timed specifications that impose explicit time bounds on the satisfaction of tasks. This work proposes and evaluates methods and algorithms for synthesizing provably correct control policies that deal with the scalability problems. Ideas and tools from formal verification, graph theory, and incremental computing are used to synthesize satisfying control strategies. Finite abstractions of the systems are generated, and then composed with automata encoding the specifications. The first part of this dissertation introduces a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The specification has two parts: (1) a global specification given as an LTL formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula, and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The second part of the dissertation focuses on stochastic systems with temporal and uncertainty constraints. A specification language called Gaussian Distribution Temporal Logic is introduced as an extension of Boolean logic that incorporates temporal evolution and noise mitigation directly into the task specifications. A sampling-based algorithm to synthesize control policies is presented that generates a transition system in the belief space and uses local feedback controllers to break the curse of history associated with belief space planning. Switching control policies are then computed using a product Markov Decision Process between the transition system and the Rabin automaton encoding the specification.The approach is evaluated in experiments using a camera network and ground robot. The third part of this dissertation focuses on control of multi-vehicle systems with timed specifications and charging constraints. A rich expressivity language called Time Window Temporal Logic (TWTL) that describes time bounded specifications is introduced. The temporal relaxation of TWTL formulae with respect to the deadlines of tasks is also discussed. The key ingredient of the solution is an algorithm to translate a TWTL formula to an annotated finite state automaton that encodes all possible temporal relaxations of the given formula. The annotated automata are composed with transition systems encoding the motion of all vehicles, and with charging models to produce control strategies for all vehicles such that the overall system satisfies the mission specification. The methods are evaluated in simulation and experimental trials with quadrotors and charging stations.

Métodos eficientes para planejamento de caminhos têm sido explorados ao longo dos anos para permitir movimento de robôs autônomos ou agentes virtuais. Basicamente, estes algoritmos buscam pelo ambiente por um caminho com pouca probabilidade de colisão com obstáculos, e que conduza o agente de uma posição inicial para uma posição objetivo. Apesar de os primeiros algoritmos para planejamento de caminhos para calcular rotas em grafos foram apresentados a mais de 50 anos atrás, ainda existe muito trabalho sendo realizado para melhorar as técnicas existentes hoje em dia. Os algoritmos de planejamento de caminhos atuais normalmente assumem que o ambiente pode ser facilmente projetado em um plano. Também existem diversos algoritmos que podem trabalhar facilmente com mais dimensões. Porém, uma classe de ambientes que não podem ser facilmente tratadas pelos algoritmos atuais é composta por superfícies arbitrárias. Estas superfícies, com buracos e torções, por exemplo, não podem ser facilmente projetadas em um plano. O fato de o caminho ser restrito à superfície faz com que, em um dado ponto o algoritmo precise calcular um caminho 2D em uma superfície 3D, o que não é trivial de mapear em um algoritmo de planejamento de caminhos para várias dimensões. Este trabalho apresenta uma nova técnica de planejamento de caminhos em superfícies 3D, chamada 3DS-BVP. Este novo planejador de caminhos é baseado em um algoritmo de planejamento de caminhos para ambientes 2D. O algoritmo anterior, chamado BVPPath- Planner, utiliza problemas de valor de contorno (Boundary Value Problems, BVP) e funções harmônicas para gerar campos potenciais. Ao seguir o gradiente descente destes campos potenciais, é possível produzir caminhos suaves livres de mínimos locais, partindo de qualquer posição do ambiente para um dado objetivo. Nosso algoritmo gera um campo potencial diretamente na superfície 3D utilizando um método numérico que foi inspirado por aquele utilizado no BVP-Path-Planner. O 3DS-BVP trabalha sobre superfícies complexas com buracos ou curvaturas, representadas por malhas de triângulos, sem a necessidade de parametrizar a superfície em uma representação 2D. Nossos resultados demonstram que a técnica pode gerar caminhos com qualidade similar àqueles gerados pelo BVP-Path-Planner em ambientes planos. O mesmo algoritmo é capaz de gerar caminhos em superfícies arbitrárias a taxas de atualização interativas. / Efficient path planning methods are being explored along the years to allow the movement of autonomous robots or virtual agents. Basically these algorithms search the environment for a path with low probability of collision with obstacles that conduces the agent from an initial to a goal position. Although the first path planning algorithms to compute routes in graphs were presented more than 50 years ago, there is still a lot of effort into improving the current approaches. The current path planning algorithms usually assume that the environment can be easily projected on a plane. There are also other algorithms that can easily deal with higher dimensional spaces. But a class of environments that cannot be easily treated by current algorithms is the one composed by arbitrary surfaces. These surfaces, with holes and bends for instance, cannot be directly projected on a plane. Because the path must be on the surface, it has only 2 degrees of freedom in any point of the surface, which is not trivial to map for a higher dimensional path planning algorithm. This work presents a new technique for path planning on 3D surfaces called 3DS-BVP. This new path planner is based on a previous path planning algorithm for 2D environments. The former algorithm, called BVP-Path-Planner, uses Boundary Value Problems (BVP) and harmonic functions to generate potential fields. By following the gradient descent of these potential fields, it is possible to produce smooth paths free from local minima from any point of the environment to a given goal position. Our algorithm generates a potential field directly on the 3D surface using a numerical method inspired on the one used by the BVP-Path-Planner. The 3DS-BVP works over complex surfaces of arbitrary genus or curvature, represented by a triangle mesh, without the need of 2D parametrizations. Our results demonstrate that our technique can generate paths with similar quality as those generated by the BVP-Path-Planner in planar environments. The same algorithm is also able to generate paths in arbitrary surfaces at interactive frame rates.

A simulação de pedestres representados como humanos virtuais em um mundo sintético é de grande interesse em áreas como cinema, arquitetura e jogos. Esta atividade pode ser definida como navegação em ambientes virtuais e envolve principalmente a especificação do ambiente, a definição da posição inicial do agente, assim como sua posição final (ou objetivo). Tendo estes parâmetros definidos, um algoritmo de planejamento de movimento, ou de caminhos, em particular, pode ser usado para encontrar uma trajetória a ser seguida por ele. Entretanto, em um mundo real, se considerar-se várias pessoas, todas na mesma posição inicial e procurando atingir o mesmo objetivo, cada uma seguirá por um caminho diferente. Ou seja, para uma mesma tarefa, a estratégia utilizada por cada pessoa para alcançar seu objetivo vai depender de sua constituição física, personalidade, humor e raciocínio. Levando em consideração estas questões, este trabalho apresenta um estudo sobre planejamento de movimento para pedestres. Como resultado prático foi desenvolvido um planejador que fornece trajetórias suaves e variadas. As trajetórias são dependentes de características individuais de cada agente, que podem ser alteradas dinâmicamente. O método adotado é baseado na utilização de campos potenciais gerados pela solução numérica de problemas de valores de contorno envolvendo a equação de Laplace (funções harmônicas) e o problema de Sturm-Liouville. Campos potenciais gerados desta forma produzem caminhos suaves e são livres de mínimos locais. O comportamento de cada agente é determinado pela alteração de seu campo potencial individual, gerado a cada passo da simulação. Dessa forma, é possível alterar dinamicamente o padrão da trajetória e ao mesmo tempo evitar colisões com obstáculos móveis (demais agentes na simulação). Por outro lado, os comportamentos gerados podem tanto ser usados de forma isolada, como combinados em movimentos complexos. Assim, é possível utilizar funções que definem trajetórias ou quantificar um desvio à esquerda ou à direita quando o agente avista um obstáculo a sua frente. A implementação do método, incluindo técnicas para controlar a velocidade e orientação do agente, e situações de simulação como comportamentos em corredores e regiões abertas, são apresentadas e discutidas. / The simulation of pedestrians represented as virtual humans in a synthetic world is of great interest in areas as cinema, architecture and games. This activity can be defined as navigation in virtual environments and involves mainly the specification of the environment, the definition of the agent’s initial position as well as its target position in the world (also called goal). By setting these parameters, a motion planning algorithm, or a path-planning algorithm in particular can be used to find a trajectory to be followed by it. However, in a real world, if we consider several persons (all in the same initial position) trying to reach the same target position, each individual path followed will be different. That is, for the same task, the strategy used by each person to reach their goal will depend on their physical constitution (body type), personality, mood and reasoning. Taking these questions into consideration, this work presents a study about motion planning for pedestrians. As a practical result, a planner which supplies smooth and varied trajectories was developed. The trajectories are also depending on the individual characteristics of each agent, which can be dynamically changed. The method adopted is based on the use of potential fields generated by numerical solutions of boundary value problems involving the equation of Laplace (harmonic functions) and the problem of Sturm- Liouville. Potential fields generated in this manner produce smooth and local minima free trajectories. The behavior of each agent is determined by the alteration of its individual potential field which is generated to each step of the simulation. Thus, it is possible to dynamically modify the standard of the trajectory and at the same time to prevent collisions with mobile obstacles (other agents in the simulation). On the other hand, the produced behaviors can be used isolatedly or combined in complex moves. Therefore, it is possible to use a function that defines a trajectory. It is also possible to quantify a detour to the left or to the right when the agent sights an obstacle ahead. The implementation of the method, including speed control techniques and agent’s orientation, and situations like simulation of behaviors in corridors or open regions, will be presented and argued.

A simulação de pedestres representados como humanos virtuais em um mundo sintético é de grande interesse em áreas como cinema, arquitetura e jogos. Esta atividade pode ser definida como navegação em ambientes virtuais e envolve principalmente a especificação do ambiente, a definição da posição inicial do agente, assim como sua posição final (ou objetivo). Tendo estes parâmetros definidos, um algoritmo de planejamento de movimento, ou de caminhos, em particular, pode ser usado para encontrar uma trajetória a ser seguida por ele. Entretanto, em um mundo real, se considerar-se várias pessoas, todas na mesma posição inicial e procurando atingir o mesmo objetivo, cada uma seguirá por um caminho diferente. Ou seja, para uma mesma tarefa, a estratégia utilizada por cada pessoa para alcançar seu objetivo vai depender de sua constituição física, personalidade, humor e raciocínio. Levando em consideração estas questões, este trabalho apresenta um estudo sobre planejamento de movimento para pedestres. Como resultado prático foi desenvolvido um planejador que fornece trajetórias suaves e variadas. As trajetórias são dependentes de características individuais de cada agente, que podem ser alteradas dinâmicamente. O método adotado é baseado na utilização de campos potenciais gerados pela solução numérica de problemas de valores de contorno envolvendo a equação de Laplace (funções harmônicas) e o problema de Sturm-Liouville. Campos potenciais gerados desta forma produzem caminhos suaves e são livres de mínimos locais. O comportamento de cada agente é determinado pela alteração de seu campo potencial individual, gerado a cada passo da simulação. Dessa forma, é possível alterar dinamicamente o padrão da trajetória e ao mesmo tempo evitar colisões com obstáculos móveis (demais agentes na simulação). Por outro lado, os comportamentos gerados podem tanto ser usados de forma isolada, como combinados em movimentos complexos. Assim, é possível utilizar funções que definem trajetórias ou quantificar um desvio à esquerda ou à direita quando o agente avista um obstáculo a sua frente. A implementação do método, incluindo técnicas para controlar a velocidade e orientação do agente, e situações de simulação como comportamentos em corredores e regiões abertas, são apresentadas e discutidas. / The simulation of pedestrians represented as virtual humans in a synthetic world is of great interest in areas as cinema, architecture and games. This activity can be defined as navigation in virtual environments and involves mainly the specification of the environment, the definition of the agent’s initial position as well as its target position in the world (also called goal). By setting these parameters, a motion planning algorithm, or a path-planning algorithm in particular can be used to find a trajectory to be followed by it. However, in a real world, if we consider several persons (all in the same initial position) trying to reach the same target position, each individual path followed will be different. That is, for the same task, the strategy used by each person to reach their goal will depend on their physical constitution (body type), personality, mood and reasoning. Taking these questions into consideration, this work presents a study about motion planning for pedestrians. As a practical result, a planner which supplies smooth and varied trajectories was developed. The trajectories are also depending on the individual characteristics of each agent, which can be dynamically changed. The method adopted is based on the use of potential fields generated by numerical solutions of boundary value problems involving the equation of Laplace (harmonic functions) and the problem of Sturm- Liouville. Potential fields generated in this manner produce smooth and local minima free trajectories. The behavior of each agent is determined by the alteration of its individual potential field which is generated to each step of the simulation. Thus, it is possible to dynamically modify the standard of the trajectory and at the same time to prevent collisions with mobile obstacles (other agents in the simulation). On the other hand, the produced behaviors can be used isolatedly or combined in complex moves. Therefore, it is possible to use a function that defines a trajectory. It is also possible to quantify a detour to the left or to the right when the agent sights an obstacle ahead. The implementation of the method, including speed control techniques and agent’s orientation, and situations like simulation of behaviors in corridors or open regions, will be presented and argued.

Métodos eficientes para planejamento de caminhos têm sido explorados ao longo dos anos para permitir movimento de robôs autônomos ou agentes virtuais. Basicamente, estes algoritmos buscam pelo ambiente por um caminho com pouca probabilidade de colisão com obstáculos, e que conduza o agente de uma posição inicial para uma posição objetivo. Apesar de os primeiros algoritmos para planejamento de caminhos para calcular rotas em grafos foram apresentados a mais de 50 anos atrás, ainda existe muito trabalho sendo realizado para melhorar as técnicas existentes hoje em dia. Os algoritmos de planejamento de caminhos atuais normalmente assumem que o ambiente pode ser facilmente projetado em um plano. Também existem diversos algoritmos que podem trabalhar facilmente com mais dimensões. Porém, uma classe de ambientes que não podem ser facilmente tratadas pelos algoritmos atuais é composta por superfícies arbitrárias. Estas superfícies, com buracos e torções, por exemplo, não podem ser facilmente projetadas em um plano. O fato de o caminho ser restrito à superfície faz com que, em um dado ponto o algoritmo precise calcular um caminho 2D em uma superfície 3D, o que não é trivial de mapear em um algoritmo de planejamento de caminhos para várias dimensões. Este trabalho apresenta uma nova técnica de planejamento de caminhos em superfícies 3D, chamada 3DS-BVP. Este novo planejador de caminhos é baseado em um algoritmo de planejamento de caminhos para ambientes 2D. O algoritmo anterior, chamado BVPPath- Planner, utiliza problemas de valor de contorno (Boundary Value Problems, BVP) e funções harmônicas para gerar campos potenciais. Ao seguir o gradiente descente destes campos potenciais, é possível produzir caminhos suaves livres de mínimos locais, partindo de qualquer posição do ambiente para um dado objetivo. Nosso algoritmo gera um campo potencial diretamente na superfície 3D utilizando um método numérico que foi inspirado por aquele utilizado no BVP-Path-Planner. O 3DS-BVP trabalha sobre superfícies complexas com buracos ou curvaturas, representadas por malhas de triângulos, sem a necessidade de parametrizar a superfície em uma representação 2D. Nossos resultados demonstram que a técnica pode gerar caminhos com qualidade similar àqueles gerados pelo BVP-Path-Planner em ambientes planos. O mesmo algoritmo é capaz de gerar caminhos em superfícies arbitrárias a taxas de atualização interativas. / Efficient path planning methods are being explored along the years to allow the movement of autonomous robots or virtual agents. Basically these algorithms search the environment for a path with low probability of collision with obstacles that conduces the agent from an initial to a goal position. Although the first path planning algorithms to compute routes in graphs were presented more than 50 years ago, there is still a lot of effort into improving the current approaches. The current path planning algorithms usually assume that the environment can be easily projected on a plane. There are also other algorithms that can easily deal with higher dimensional spaces. But a class of environments that cannot be easily treated by current algorithms is the one composed by arbitrary surfaces. These surfaces, with holes and bends for instance, cannot be directly projected on a plane. Because the path must be on the surface, it has only 2 degrees of freedom in any point of the surface, which is not trivial to map for a higher dimensional path planning algorithm. This work presents a new technique for path planning on 3D surfaces called 3DS-BVP. This new path planner is based on a previous path planning algorithm for 2D environments. The former algorithm, called BVP-Path-Planner, uses Boundary Value Problems (BVP) and harmonic functions to generate potential fields. By following the gradient descent of these potential fields, it is possible to produce smooth paths free from local minima from any point of the environment to a given goal position. Our algorithm generates a potential field directly on the 3D surface using a numerical method inspired on the one used by the BVP-Path-Planner. The 3DS-BVP works over complex surfaces of arbitrary genus or curvature, represented by a triangle mesh, without the need of 2D parametrizations. Our results demonstrate that our technique can generate paths with similar quality as those generated by the BVP-Path-Planner in planar environments. The same algorithm is also able to generate paths in arbitrary surfaces at interactive frame rates.

Métodos eficientes para planejamento de caminhos têm sido explorados ao longo dos anos para permitir movimento de robôs autônomos ou agentes virtuais. Basicamente, estes algoritmos buscam pelo ambiente por um caminho com pouca probabilidade de colisão com obstáculos, e que conduza o agente de uma posição inicial para uma posição objetivo. Apesar de os primeiros algoritmos para planejamento de caminhos para calcular rotas em grafos foram apresentados a mais de 50 anos atrás, ainda existe muito trabalho sendo realizado para melhorar as técnicas existentes hoje em dia. Os algoritmos de planejamento de caminhos atuais normalmente assumem que o ambiente pode ser facilmente projetado em um plano. Também existem diversos algoritmos que podem trabalhar facilmente com mais dimensões. Porém, uma classe de ambientes que não podem ser facilmente tratadas pelos algoritmos atuais é composta por superfícies arbitrárias. Estas superfícies, com buracos e torções, por exemplo, não podem ser facilmente projetadas em um plano. O fato de o caminho ser restrito à superfície faz com que, em um dado ponto o algoritmo precise calcular um caminho 2D em uma superfície 3D, o que não é trivial de mapear em um algoritmo de planejamento de caminhos para várias dimensões. Este trabalho apresenta uma nova técnica de planejamento de caminhos em superfícies 3D, chamada 3DS-BVP. Este novo planejador de caminhos é baseado em um algoritmo de planejamento de caminhos para ambientes 2D. O algoritmo anterior, chamado BVPPath- Planner, utiliza problemas de valor de contorno (Boundary Value Problems, BVP) e funções harmônicas para gerar campos potenciais. Ao seguir o gradiente descente destes campos potenciais, é possível produzir caminhos suaves livres de mínimos locais, partindo de qualquer posição do ambiente para um dado objetivo. Nosso algoritmo gera um campo potencial diretamente na superfície 3D utilizando um método numérico que foi inspirado por aquele utilizado no BVP-Path-Planner. O 3DS-BVP trabalha sobre superfícies complexas com buracos ou curvaturas, representadas por malhas de triângulos, sem a necessidade de parametrizar a superfície em uma representação 2D. Nossos resultados demonstram que a técnica pode gerar caminhos com qualidade similar àqueles gerados pelo BVP-Path-Planner em ambientes planos. O mesmo algoritmo é capaz de gerar caminhos em superfícies arbitrárias a taxas de atualização interativas. / Efficient path planning methods are being explored along the years to allow the movement of autonomous robots or virtual agents. Basically these algorithms search the environment for a path with low probability of collision with obstacles that conduces the agent from an initial to a goal position. Although the first path planning algorithms to compute routes in graphs were presented more than 50 years ago, there is still a lot of effort into improving the current approaches. The current path planning algorithms usually assume that the environment can be easily projected on a plane. There are also other algorithms that can easily deal with higher dimensional spaces. But a class of environments that cannot be easily treated by current algorithms is the one composed by arbitrary surfaces. These surfaces, with holes and bends for instance, cannot be directly projected on a plane. Because the path must be on the surface, it has only 2 degrees of freedom in any point of the surface, which is not trivial to map for a higher dimensional path planning algorithm. This work presents a new technique for path planning on 3D surfaces called 3DS-BVP. This new path planner is based on a previous path planning algorithm for 2D environments. The former algorithm, called BVP-Path-Planner, uses Boundary Value Problems (BVP) and harmonic functions to generate potential fields. By following the gradient descent of these potential fields, it is possible to produce smooth paths free from local minima from any point of the environment to a given goal position. Our algorithm generates a potential field directly on the 3D surface using a numerical method inspired on the one used by the BVP-Path-Planner. The 3DS-BVP works over complex surfaces of arbitrary genus or curvature, represented by a triangle mesh, without the need of 2D parametrizations. Our results demonstrate that our technique can generate paths with similar quality as those generated by the BVP-Path-Planner in planar environments. The same algorithm is also able to generate paths in arbitrary surfaces at interactive frame rates.

A simulação de pedestres representados como humanos virtuais em um mundo sintético é de grande interesse em áreas como cinema, arquitetura e jogos. Esta atividade pode ser definida como navegação em ambientes virtuais e envolve principalmente a especificação do ambiente, a definição da posição inicial do agente, assim como sua posição final (ou objetivo). Tendo estes parâmetros definidos, um algoritmo de planejamento de movimento, ou de caminhos, em particular, pode ser usado para encontrar uma trajetória a ser seguida por ele. Entretanto, em um mundo real, se considerar-se várias pessoas, todas na mesma posição inicial e procurando atingir o mesmo objetivo, cada uma seguirá por um caminho diferente. Ou seja, para uma mesma tarefa, a estratégia utilizada por cada pessoa para alcançar seu objetivo vai depender de sua constituição física, personalidade, humor e raciocínio. Levando em consideração estas questões, este trabalho apresenta um estudo sobre planejamento de movimento para pedestres. Como resultado prático foi desenvolvido um planejador que fornece trajetórias suaves e variadas. As trajetórias são dependentes de características individuais de cada agente, que podem ser alteradas dinâmicamente. O método adotado é baseado na utilização de campos potenciais gerados pela solução numérica de problemas de valores de contorno envolvendo a equação de Laplace (funções harmônicas) e o problema de Sturm-Liouville. Campos potenciais gerados desta forma produzem caminhos suaves e são livres de mínimos locais. O comportamento de cada agente é determinado pela alteração de seu campo potencial individual, gerado a cada passo da simulação. Dessa forma, é possível alterar dinamicamente o padrão da trajetória e ao mesmo tempo evitar colisões com obstáculos móveis (demais agentes na simulação). Por outro lado, os comportamentos gerados podem tanto ser usados de forma isolada, como combinados em movimentos complexos. Assim, é possível utilizar funções que definem trajetórias ou quantificar um desvio à esquerda ou à direita quando o agente avista um obstáculo a sua frente. A implementação do método, incluindo técnicas para controlar a velocidade e orientação do agente, e situações de simulação como comportamentos em corredores e regiões abertas, são apresentadas e discutidas. / The simulation of pedestrians represented as virtual humans in a synthetic world is of great interest in areas as cinema, architecture and games. This activity can be defined as navigation in virtual environments and involves mainly the specification of the environment, the definition of the agent’s initial position as well as its target position in the world (also called goal). By setting these parameters, a motion planning algorithm, or a path-planning algorithm in particular can be used to find a trajectory to be followed by it. However, in a real world, if we consider several persons (all in the same initial position) trying to reach the same target position, each individual path followed will be different. That is, for the same task, the strategy used by each person to reach their goal will depend on their physical constitution (body type), personality, mood and reasoning. Taking these questions into consideration, this work presents a study about motion planning for pedestrians. As a practical result, a planner which supplies smooth and varied trajectories was developed. The trajectories are also depending on the individual characteristics of each agent, which can be dynamically changed. The method adopted is based on the use of potential fields generated by numerical solutions of boundary value problems involving the equation of Laplace (harmonic functions) and the problem of Sturm- Liouville. Potential fields generated in this manner produce smooth and local minima free trajectories. The behavior of each agent is determined by the alteration of its individual potential field which is generated to each step of the simulation. Thus, it is possible to dynamically modify the standard of the trajectory and at the same time to prevent collisions with mobile obstacles (other agents in the simulation). On the other hand, the produced behaviors can be used isolatedly or combined in complex moves. Therefore, it is possible to use a function that defines a trajectory. It is also possible to quantify a detour to the left or to the right when the agent sights an obstacle ahead. The implementation of the method, including speed control techniques and agent’s orientation, and situations like simulation of behaviors in corridors or open regions, will be presented and argued.

A teleoperated system of dual redundant manipulator will be controlled in this thesis. The robot used with the dual redundant manipulator in this thesis is Baxter. Baxter’s redundant robot arms are 7-degree-of-freedom arms. The problem that will be solved in this thesis is optimization of the 7-degree-of-freedom robot arms. The control algorithm of the 7-degree-of-freedom robot arms will be discussed and built. A simulation program will be built to test the control algorithm. Based on the control algorithm, a teleoperation system will be created for Baxter. The controller used is Omni, which is a six-joint haptic device. Omni will also be used to give force feedback upon collision while the user is controlling the robot. Hence, a collision force feedback system is going to be created and combined with the teleoperation system. The teleoperation system will be tested in common daily applications.

[EN] The efficiency of free-collision motion planning results very sensible on robot and obstacle modelling technique selected. In this way, many works have been oriented to define models with proper throughput to speed up the collision detection proccess. This dissertation presents a new approach to the problem, whose complexity is reduced notably by means of using enveloping models of real objects, allowing security regions or distances. This objective is reached by means of the definition of a spherical model, composed of infinite spheres, generated from the application of linear or polynomial equations to a reduced number of control spheres, giving the so-called poly-spheres and spheroids respectively. These models, with evident simplicity, present a high modelling power, adapt easily to the requirements need in collision-detection and path planning applications for robotics systems. In order to represent a complete multi-robot cell, an extended hierarchical structure has been defined, in form of an AND-OR graph, with different degrees of accuracy, according to the different approximation model used. In order to generate automatically this structure, a procedure has been developed to compute the minimum volume enveloping spherical model in an off-line process with two levels based on Downhill Simplex method and Hough transform. This procedure can be greatly speed up by using clustering techniques to obtain appropiate initial conditions, allowing an on-line use. With a hierarchical structure computed in such a way, a fast procedure for collision detection in a multi-robot cell is introduced, based on several algorithms for distance computation including polyspheres and spheroids. This methodology presents a fast and anticipativa response, in the sense that every movement of a system has been validated before its execution, implying that not necessarily must be done in an off-line simulation. The use of spherical models, in addition to their fast distance computation, results suitable for the definition of artificial potential fields allowing a path planning in robotics systems with up to six degrees of freedom, including three for translation and three for rotation. The definition of these new potential fields and the study of new planning techniques based on classical optimisation methods allow their application straight forward in Cartesian space, with all their advantages. Last but not least, with the help of some systems for robot programming, simulation and control, the correctness of these contributions have been validated in a set of prototype applications, covering from robot-obstacle and multi-robot collision detection, to motion planning for a robot-arm or an auto-guided vehicle. / [ES] La eficiencia de la planificación de movimientos libres de colisión resulta muy sensible al modelado de los robots y obstáculos que se consideren, por lo que, frente al modelado tradicional con politopos, muchos trabajos en robótica han estado orientados a la definición de unos modelos que presenten buenas prestaciones de cara a acelerar el proceso de detección de colisiones. En esta Tesis se presenta una nueva perspectiva del problema, cuya complejidad queda reducida notablemente al utilizar envolventes de los objetos reales, lo que permite definir zonas o distancias de seguridad. Para ello se han definido unos modelos esféricos, compuestos de infinitas esferas generadas a partir de la aplicación de unas relaciones lineales o polinómicas a un número reducido de esferas de control, dando lugar a las llamadas poli-esferas y esferoides respectivamente. Estos modelos, de sencillez clara, presentan una potencia de modelado elevada, adaptándose fácilmente a los requisitos necesarios en las aplicaciones de detección de colisiones y planificación de movimientos en sistemas robotizados. Para la representación de una célula multi-robot completa, se ha definido una estructura jerárquica extendida, en forma de grafo AND-OR, con diferentes grados de precisión, mediante diferentes modelos de aproximación. De cara a generar automáticamente esta estructura, se ha desarrollado un procedimiento para generar el modelo esférico envolvente de mínimo volumen en un proceso off-line con dos niveles, basados en el método de minimización Downhill Simplex y en la transformada de Hough. Este procedimiento se acelera enormemente al utilizar técnicas de agrupamiento para obtener condiciones iniciales apropiadas, permitiendo su uso on-line. Con una estructura jerárquica generada de esta forma, se introduce un procedimiento rápido de detección de colisiones aplicable a una célula multi-robot, basado en algoritmos básicos de cálculo de distancias que pueden considerar poli-esferas y esferoides. Esta metodología presenta una respuesta rápida y anticipativa, entendiendo por tal que todo movimiento de cualquier sistema ha sido validado antes de su ejecución, por lo que no necesariamente debe realizarse en una simulación off-line. La utilización de modelos esféricos, así como el rápido cálculo de distancias entre ellos, resulta idónea para la definición de campos potenciales artificiales que permitan una planificación de movimientos en sistemas robotizados con hasta seis grados de libertad, incluyendo tres de traslación y tres de rotación. La definición de estos nuevos campos potenciales y el estudio de nuevas técnicas de planificación basados en métodos clásicos de optimización permiten su aplicación directamente en el espacio cartesiano, con las claras ventajas que esto conlleva. Finalmente, con la ayuda de varios sistemas de programación, simulación y control de robots, se ha demostrado la validez de estas aportaciones en una serie de aplicaciones prototipo que van desde la detección de colisiones de un robot con un obstáculo o entre sistemas multi-robot, a la planificación de movimientos de un brazo-robot o un vehículo autoguiado. / Mellado Arteche, M. (1996). Modelado, detección de colisiones y planificación de movimientos en sistemas robotizados mediante volúmenes esféricos [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/56621

This diploma project is focused on possible applications of computational geometry methods for robot motion planning among static and dynamic obstacles, particularly based on global robot motion planning by means of generalised Voronoi diagrams. The main effort was to convert this complex geometric and analytic problem to graph theory environment where the tasks of planning and searching paths between pairs of the graph vertices are effeciently solvable. The Voronoi diagram is created considering the whole searching space, while edges of this diagram satisfy that the distance from the surrounding obstacles is maximised and the path found along the Voronoi diagram edges is optimised from the point of view of its security (and it is collision-free).