Motion-planning

De Wiki-II

Tabela de conteúdo

Semi-Automatic Navigation on 3D Triangle Meshes Using BVP Based Path-Planning

Semi-Automatic Navigation on 3D Triangle Meshes Using BVP Based Path-Planning
  • Article published in the XXIV SIBGRAPI – Conference on Graphics, Patterns and Images (SIBGRAPI 2011)
  • Authors:
  • Abstract: Efficient path-planning methods are being explored along the years to allow the movement of robots or virtual agents in planar environments. However, there is a lot of space to improve the quality of paths restricted to 3D surfaces, with holes and bends for instance. This work presents a new technique for path-planning on 3D surfaces called 3DS-BVP. This path planner is based on Boundary Value Problem (BVP), which generates potential fields whose gradient descent represents navigation routes from any point on the surface to a goal position. Resulting paths are smooth and free from local minima. The 3DS-BVP works on 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 in arbitrary surfaces with similar quality as those generated by BVP-based methods in planar environments. Our approach can be applied in the development of new tools to automate the navigation on 3D surfaces, like the camera control in the exploratory visualization of 3D models.
  • Full text at Sibgrapi digital archive
  • Reference in BibTeX format


Path-Planning for RTS Games Based on Potential Fields

Path-Planning for RTS Games Based on Potential Fields
  • Article published in Third International Conference on Motion in Games (MIG 2010)
  • Authors:
  • Abstract: Many games, in particular RTS games, are populated by synthetic humanoid actors that act as autonomous agents. The navigation of these agents is yet a challenge if the problem involves finding a precise route in a virtual world (path-planning), and moving realistically according to its own personality, intentions and mood (motion planning). In this paper we present several complementary approaches recently developed by our group to produce quality paths, and to guide and interact with the navigation of autonomous agents. Our approach is based on a BVP Path Planner that generates potential fields through a differential equation whose gradient descent represents navigation routes. Resulting paths can deal with moving obstacles, are smooth, and free from local minima. In order to evaluate the algorithms, we implemented our path planner in a RTS game engine
  • Full text at SpringerLink
  • Reference in BibTeX format
  • Video at Vimeo


Fast Path Planning using Multi-Resolution Boundary Value Problems

Fast Path Planning using Multi-Resolution Boundary Value Problems
  • Article published in The 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010)
  • Authors:
  • Abstract: BVP Path Planners generate potential fields through a differential equation whose gradient descent represents navigation routes from any point of the environment to a goal position. Resulting paths are smooth and free from local minima. In spite of these advantages, this kind of planners consumes a lot of time to produce a solution. In this paper, we present a new approach that combines our BVP Path Planner with the Full Multigrid Method, which solves elliptic partial differential equations using a hierarchical strategy. Our new approach is called Hierarchical BVP Path Planner and it enables a real-time performance on large environments. The results show that our proposal spends less than 1% of the time needed to compute a solution using our original planner in several environments.
  • Full text at IEEE Xplore
  • Reference in BibTeX format


Natural steering behaviors for virtual pedestrians

Natural steering behaviors for virtual pedestrians
  • Article published in The Visual Computer, TVC'2010
  • Authors:
  • Abstract: The animation of humanoids in real-time applications is yet a challenge if the problem involves attaining a precise location in a virtual world (path-planning), moving realistically according to its own personality, intentions and mood (motion planning). In this paper we propose a formally complete and low-cost solution based upon boundary value problems (BVP) to control steering behaviors of characters in dynamic environments. We use a potential field formalism that allows synthetic actors to move negotiating space, avoiding collisions, and attaining goals, while producing very individual paths. The individuality of each character can be set by changing its inner field parameters leading to a broad range of possible behaviors without jeopardizing its performance. To illustrate the technique potentialities, some results exploring situations as steering behavior in corridors with collision avoidance and competition for a goal, and searching for objects in unknown environments are presented and discussed. A proposal to automatically change the size of the field of view of each agent, producing different behaviors is also a contribution of this paper. Some comments about performance are also made to help the reader to evaluate the potential of the method.
  • Full text at SpringerLink
  • Reference in BibTeX format
  • Video at Vimeo


GPU Accelerated Path-planning for Multi-agents in Virtual Environments

GPU Accelerated Path-planning for Multi-agents in Virtual Environments
  • Article published in the VIII Brazilian Symposium on Games and Digital Entertainment (SBGAMES 2009)
  • Authors:
  • Abstract: Many games are populated by synthetic humanoid actors that act as autonomous agents. The animation of humanoids in real-time applications is yet a challenge if the problem involves attaining a precise location in a virtual world (path-planning), and moving realistically according to its own personality, intentions and mood (motion planning). In this paper we present a strategy to implement – using CUDA on GPU – a path planner that produces natural steering behaviors for virtual humans using a numerical solution for boundary value problems. The planner is based on the potential field formalism that allows synthetic actors to move negotiating space, avoiding collisions, and attaining goals, while producing very individual paths. The individuality of each character can be set by changing its inner field parameters leading to a broad range of possible behaviors without jeopardizing its performance. With our GPU-based strategy we achieve a speed up to 56 times the previous implementation, allowing its use in situations with a large number of autonomous characters, which is commonly found in games.
  • Full text
  • Reference in BibTeX format
  • Presentation
  • Source code


Performance optimization in path planners using potential fields

  • Original title (in portuguese): Otimização de desempenho em planejadores de caminho usando campos potenciais
  • Work published as a prerequisite for bachelor's degree, 2008
Otimização de desempenho em planejadores de caminho usando campos potenciais
  • Author: Leonardo Garcia Fischer
  • Abstract: The autonomous agent animation concerns many areas, such as movies, games and simulations. Its main objective is how to define methods of reproducing a certain being in a realist way (be it alive, mechanic or even imaginary). Several techniques have al-ready been proposed in order to achieve high quality in the final animation. However, we can notice that these proposals are more and more complex, which difficults its use in real time applications. Thus, the algorithm's performance which accomplishes the animation can be as im-portant as the quality of the animation itself. A technique which produces high quality results, though it cannot be performed in real time, will be limited enough when it comes to applicability. Therein, this work shows the study of one of these algorithms, featuring a way of improving its performance and aiming at using it in real time applications. This perfor-mance advantage will be achieved by using parallel characteristics of the algorithm. Then, this work uses the actual video boards' high parallelism to extend Dapper's work (DAPPER et al., 2007). In his work, Dapper used the potential fields developed from a numerical solution of boundary value problems involving the Laplace's equation (harmonic functions). These potential fields can create paths with mild courses, free of local minimun. Because of this they were used to produce the path to be followed by the autonomous agent. As we will see, these potential fields can be achieved much more quickly if we parallelize the calculations involved in. It will be presented as well a series of tests which showed that the algorithm's paral-lel implementation can improve its performance. The tests showed that the new imple-mentation is up to 56 times faster than the sequential implementation. This makes the algorithm applicable for use in real time, even in situations with thousands of autonom-ous agents in the scene. Finally, a set of other contributions made to the project will be showed, among which two of them stand out: a system of ramification of paths to define routes and the improvement of the already existent code as a form of enriching later works.
  • Full text (portugueses only)
  • Source code


High-Level Path Specification and Group Control for Virtual Characters in Interactive Virtual Environments

High-Level Path Specification and Group Control for Virtual Characters in Interactive Virtual Environments
  • Article published in the Computer Graphics International, CGI'2008
  • Authors:
  • Abstract: Social rules such as following the same path, moving towards a common objective, and moving while keeping a formation are some desirable steering behaviors for the simulation of interactive groups. Moreover, interaction with groups in real-time applications is also a challenge, since hundreds of units should be controlled urgently and efficiently. We propose a robust algorithm to control themovement of groups in interactive environments and a strategy to keep their formations while moving. Our method is based on potential fields and has two layers. In the first one, a formation map is built to allow for local control of each individual, while in the second a path planning is performed for each group as a whole. The technique proposed combines motion planning for groups with sketch-based navigation control. Results show that our technique is robust to several situations and can be implemented on GPU, which results in real-time performance for large groups.
  • Full text at Renato Silveira's Home Page
  • Reference in BibTeX format

Managing coherent groups

Managing coherent groups
  • Article published in Computer Animation and Virtual Worlds, CASA'2008
  • Authors:
  • Abstract: The animation of groups of characters involves the generation of some interesting steering behaviors like following a single path, moving toward a common objective, and moving while keeping a formation. This paper presents a new approach to manage the movement of groups in dynamic environments using a simple and robust algorithm that includes a strategy to keep formations during the displacement of the group. Our method is based on a boundary value problem (BVP) involving Laplace's equation and has two layers. In the first one, a group map is built to allow for local control of each individual, while in the second one a path planning is performed for each group as a whole. Results show that our technique is robust to several situations and can be implemented on GPU, which results in real-time performance for large groups.
  • Full text at Wiley InterScience
  • Reference in BibTeX format
  • Video at Vimeo

A Sketch-based Interface to Real-time Strategy Games Based on a Cellular Automaton

A Sketch-based Interface to Real-time Strategy Games Based on a Cellular Automaton
  • Article published in the book Game Programming Gems 7 (2008)
  • Authors:
  • Abstract: Real-time strategy games (RTS) are one of the most popular game genres of the world. The combination of action and strategy is simply addictive, with lots of devoted players spending days on game campaigns or instant battles over the net. We are not seeing, however, significant improvements in the RTS gameplay in recent years. By comparing a recent title to the very early ones, we can say that now we have more units on the screen (maybe hundreds of them), new beautiful graphical engines, and wider battlefields than ever before, but the essence of the gameplay is still the same: selecting units and defining their tasks just clicking with the mouse. This process entails a very simple and efficient interface, on which players are usually well trained, but what should we do when the game demands more? How can we control hundreds of units in a realistic and efficient way? And since the interface is designed for hand-to-hand combat, what should we do when the army becomes huge and there is no clear idea about its disposal? We are facing such situations in current game titles, and despite recent improvements, common unit-based interfaces sometimes let players frustrated. In this work we describe an alternative to improve gameplay in such situations. We propose a one-click higher-level interface that controls the movement of entire armies or groups of soldiers. The idea behind our approach is very simple, and can be illustrated with any battlefield map from the old history books.
  • Full text at book Game Programming Gems 7, Charles River Media, 2008, v. 1, p. 39-48
  • Video at Vimeo


Generating Steering Behaviors for Virtual Humanoids using BVP Control

Generating Steering Behaviors for Virtual Humanoids using BVP Control
  • Article published in the 25th Computer Graphics International Conference (CGI'2007)
  • Authors:
  • Abstract: One of the main challenges on animating embodied autonomous characters in real-time applications is the ability to generate believable behaviors, more precisely, actors capable of moving in a natural and improvisational manner. In this paper we propose an elegant and low cost solution based upon boundary value problems (BVP) to control steering behaviors of characters.We use a field potential formalism that allows synthetic actors to move negotiating space, avoiding collisions, and attaining goals, while producing very individual paths. The individuality of each character can be set by changing its inner field parameters leading to a broad range of possible behaviors. To illustrate the technique potentialities, some results exploring situations as steering behavior in corridors with collision avoidance and competition for a goal, and searching for objects in unknown environments are presented and discussed.
  • Full text at INF UFRGS
  • Reference in BibTeX format


Simulating Pedestrian Behavior with Potential Fields

Simulating Pedestrian Behavior with Potential Fields
  • Article published in the 24th Computer Graphics International Conference, CGI 2006
  • Authors:
  • Abstract: The main challenges of realistically simulating the displacement of humanoid pedestrians are twofold: they need to behave realistically and they should accomplish their tasks. Here we present a field potential formalism, based upon boundary value problems, that allows a group of synthetic actors to move negotiating space, avoiding collisions, attaining goals in prescribed sequences while at same time producing very individual paths. The individuality of each pedestrian can be set by changing its inner field parameters. This leads to a broad range of possible behaviors without jeopardizing its task performance. Simulate situations as behavior in corridors, collision avoidance and competition for a goal are presented and discussed.
  • Full text:
  • Reference in BibTeX format
Ferramentas pessoais