Reactive Navigation Mash-up

I've been reading some papers recently which try to solve the reactive local navigation by finding obstacle interference in different spaces by using some co-operative methods. Here's a couple of those papers.

• Extending Obstacle Avoidance Methods through Multiple Parameter-Space Transformations
• Reactive Navigation of Multiple Moving Agents by Collaborative Resolution of Conflicts
• Cooperative Navigation Function based Navigation on Multiple Mobile Robots
• Multi Robotic Conflict Resolution by Cooperative Velocity and Direction Control

Hexmoor and Krishna has a multituple of other papers on their approach too. Can be found via Hexmoor's publications page.

Space Transformations
Parameter space transformation feels like something that could be a good base for local avoidance using animation driven motion. The rough idea is that you have a parametrized trajectory, it could be an arc or two-point-turn or anything else, and you transform obstacles in the world to a space where the trajectory is one dimension and the parameter another.

My TOI sampling method basically does that using straight trajectories. Another notable velocity space local navigation method is Dynamic Window Approach.

Co-operation for Conflict Resolution
The good and the bad of many reactive obstacle avoidance methods are that they are local, egocentric. You don't need much information from other agents in order to avoid them. That was the good bit.

The hard thing is that it often results flickering solutions. A classic example is playing chicken, that is two agents move towards each other and they should avoid to not collide (similar case is also if a faster agent tries to overtake slower one). One potential solution is that both agents choose to avoid each other from the same side, on the next iteration 50 ms later they decide to avoid from the others. They will continue this until they eventually collide.

RVO, HRVO and many other methods have been proposed to solve the case. Krishna's and Hexmoor's work continue that saga by using additional graph structure to solve the conflicts. I'm still digesting Khrisna's and Hexmoor's solution, but I brought me an idea.

Reactive Navigation as Collision Response Problem
The first impression I got from the co-operative graph method was islands used in collision detection, then I remembered the different spaces where collisions can be detected and the next thing obvious thing was an idea combining the two and bringing aboard few things from collision detection.

One way to look at the navigation problem is to think it in 3D space, where x,y and cartesian coordinates of an agent and z is time. In that space-time world, the agents become skewed cylinders.

Now that our aim is to create collision free paths in that space, we can do that simply by doing collision detection and response in that space. So I went and prototyped that and it kinda works pretty well in simple test cases. The result was boring 4 agents crossing each other and bumping into things (yay!) as can witnessed in the following picture.


I used similar iterative method as you would use for verlet collision detection. For each pair (i,j) of agents, I calculate the nearest location along their velocities:

vab = ai.vel - aj.vel
closestPt_PointRay(aj.pos, ai.pos, vab, t)
hiti = ai.pos + ai.vel*t
hitj = aj.pos + aj.vel*t

After tha I proceed with the usually circle-circle collision response by moving them apart and that new resolved location is the new heading of the agent. Shake it for a dosen iterations and you have resolved your future collisions. When the agents are really close to each other the result is steering away from the other agent. This leads to some jags in the path (as can be seen in the picture too).

Ideally this method should also allow to include the time into the response equation. If an agent is moving into some direction that results nicely skewed cylinder, not if the agents location in the future is the same as current one, then the cylinder is not skewed at all. I have not quite figured out how to make the collisions to affect time, but maybe there is a good way to do that.

Introducing Project Cane

I just added "Project Cane" [1] into Google code. The goal of that project is to implement and explore different local navigation methods and bet them against each other.

I also hope to gather a good selection of realistic test cases in the process. Something that I have seen to cause problems before and something that turns out while testing new code. Eventually the result of this project will end up as a module for Detour.

The code is quick and dirty. If you want to reuse the code in your project I encourage to reimplement it. If you have something to contribute, say, port of existing local navigation method, some test cases, your favorite steering method, let me know and I'll give you access.


The current implementation includes the TOI sampling based method I have been blogging about recently. It works in many cases pretty well, but produces ugly results under certain cases and with certain parameters.

One of the biggest drawback is the sampling. For example try out the example chicken_corridor.txt with fewer samples (say, 32) and it gets rather ugly. It seems to be crucial to get the tiny features right, in order to make the local navigation robust in constrained areas.

Another thing that is causing weird behavior is that the method makes the assumption that moving at constant speed is a good thing. While it makes sense (and some papers refer to that assumption too), in some cases it just creates movement which is not what I expect.

I'll be adding my HRVO implementation as soon as I get it to work with segments too.

_

In general, I'm not quite satisfied with any method I have tried so far. Interestingly, many of then can be tuned so that they will solve the specific tests cases nicely. And usually the tuning has to do with how to handle tiny details in velocity handling.

In certain cases it is beneficial to filter out higher frequency details to create steady and flicker free velocity selection, but sometimes the right solution can only be found by looking at the fine details (such as the case mentioned above).

Usually my attention in this kind of cases turns into some sort of hierarchical methods. Translating that to the above problem, I could be possible to downsample the sampled TOIs and use that to select a rough sector where the velocity will be selected from and then use the more accurate samples to refine the selection. Velocity selection is really hard problem. No wonder that most of the studies eventually resort to search (i.e. see: VFH, VFH+, VFH*).

After a steady progress of research, I feel that I'm back to square one again, maybe a bit wiser this time around.

___

[1] Yes, I'm fan of Md. House and local navigation is like poking around with a cane anyways.

Stumbling Towards the Holidays

After a small hiatus, I've been grinding off my to-do list. The first item was to finish the local navigation proto.

Firstly, I implemented static segment obstacles into my testbed to create more realistic scenarios. The outcome was badly stuck agents. It was way worse than I expected it to be.

After adding the graph based steering helper from my previous post, things got immediately much better. You can see that in action at the end of the video. The obstacle graph is the extra blobs, connected by arcs. The connected islands are formed and each labeled using simple graph flood fill. It would be necessary to tesselate the edge segments as in the video, but I was testing original idea and they just kinda got left out there.

Instead of the graph walk, I use similar method as in Oriented Visibility Graphs to calculate the new desired movement direction (longish white arrow in the video). The cool thing is that my version it can handle many kinds of local minimas, but not all.

The result from the obstacle graph is somewhat present in the TOI sampling too, I wonder if it would be possible to combine the two algorithms.

I hope I can squeeze out few evenings during the holidays and finish off and release the proto.

Before that happens, thank you for all you who have followed and commented this blog, I hope to get good pace of postings coming up next year, too. Until then,

Merry Merry, Happy Happy and New Year too!

Recast Debug Draw Changed

I used submitted a change to the SVN where I moved the debug draw functions to a separate folder DebugUtils. Now also the Detour debug draw stuff uses the same abstract interface so it is free of any DSL and OpenGL dependancies.

As an added bonus, I also added a couple of functions to dump the Recast poly mesh as well as the poly mesh detail as an .obj file.

[EDIT] Of course there were some missing files in that change list. Revision 86 has all the needed fioes.

Improving Local Avoidance

Chris Paulson asked in the comments of another post how to improve steering based local avoidance. The reply grew quite large, so I thought I'd put it here as another post instead.

All kinds of local steering behaviors have the problem of getting stuck at local minima. That is what Chris is experiencing too, and that is what my recent research is trying to solve.

When splitting the system in reactive (local) and planning (path finding on static graph) navigation, the level of detail where the split happens is important. If the high level plan is too coarse, the local planning is not able to resolve. I think that is what Chris is experiencing.

I have noticed that agents usually do not resolve from local minimas, which are twice as large as their radius. For example two barrels next to each other are still ok to avoid locally, but if they are spaced more widely, so that the agent still cannot move through them, then they may be too big an obstacle. Add another barrel or wall to make it a a but more U-shaped and you get a case which is not easily solvable using reactive local navigation.

Local and Global Navigation

My reasoning has always been that as long as the results would be unpredictable anyways, use local navigation. Moving obstacles are always avoided locally, since at least in game environment we can assume that their movement is unpredictable.

Once they come to rest and touch other objects, they should be included in the planning level navigation graph. The Recast/Detour way is to update a tile once something has changed in it. As an example see Yakov's work.

The reasoning is to try to make it as simple as possible. Modifying the navigation mesh allows the rest of the system to always use the same format of navigation data. Obstacles that change the planning graph does not need to be special cased in the code.

Alternative to rebuilding a whole tile is the just cut holes into it. Cutting holes to polygons is not exactly very easy to get right. That cookie cutter method is limited to only obstruct movement, not allow it. For those reasons (and because Recast is pretty fast ;)), my preferred solution is to build small piece of the navigation mesh every time it is necessary. In contrast to Yakov's work, I probably would not update the mesh as often as he is doing.

Obstacle Graph

If dynamic mesh updates shy you away, or you simply cannot do that. Local navigation can be enhanced to help out to avoid getting stuck at local minima. One way is to add additional representation for it, for example see [1]. Another, maybe simpler idea would be to find islands touching obstacles, calculate their boundary, and steer towards the next "shadow boundary" of the obstacle island.

This proposed method has certain similarities with [2], which Google surfaced for me when I was searching about points of visibility graphs (there were a recent discussion about then at AIGameDev.com).

As an example take a look at the picture at the top of this post. There the orange agent is trying to avoid set of barrels. Most reactive local navigation methods would probably steer the character left into the local minima between the left most barrel and the wall.

To aid this situation, it is possible to calculate a graph of all the obstacles which are touching (check using obstacle radius plus agent radius). Then sort all the links per each obstacle based on their angle.

Using this data it is possible to locate the navigating agent by finding its' spot between two links at the nearest obstacle in the graph. Then you can follow the contour of the obstacle island by always choosing the next adjacent link left or right (that is, in the sorted per obstacle list if links) depending on which direction we want to traverse the object. This traversal will lead us to follow the contour of the obstacle because the links were sorted.

During the traversal, we can find the max steering angle left and right. Steering towards this angle will lead us out of any local minima. It is also possible to calculate the winding of the traversal and check if the agent is inside or outside a set of obstacles. If the traversal code hits a wall should make the steering and in that direction invalid. If both sides are blocked, we know that the link from current navigation node/polygon to the next one is blocked.

One way to resolve from this is to then temporarily disable the link and replan. The temporary disable could last a until certain time has passed, or until any of the objects move in the island have moved. It is really important to get this feedback part right. If you get stuck in local navigation, you should never replan unless you can fix that issue in global graph!

My favorite still is to adjust the navmesh even if it is a bit more complicated to implement.


[1] Automated static and dynamic obstacle avoidance in arbitrary 3D polygonal worlds
[2] Oriented Visibility Graphs: Low-Complexity Planning in Real-Time Environments

Detour Cleanup Complete

I just committed few changes to the SVN, which removes dtStatNavmesh and dtTileNavmesh. The brand new dtNavMesh has combined functionality if the both.

Migration should be as easy as renaming dtStat* or dtTile* to dt*. There are two different init() methods depending if you use the mesh as solo or tile based.

dtNavMesh now also has BVtree per tile mesh for faster polygon lookup, which is good news if you are using large tile sizes. The tile mesh limitations, max tile and poly count, are now parameters which can be set at runtime. The max node count for the A* is not init param too, instead of magic constant in the sources.

The reason for this merging was that it was becoming a burden to manage the two types of meshes which were supposed to have the same functionality.

I apologize again for the trouble.

Constrained Movement Along Path Corridor

I just added simple path iterator code for Detour. I have been postponing this Detour feature for quite some time now since I was not sure how my recent research on obstacle avoidance would affect it.

Even if path following sounds easy, it can be really hard to get to work on all cases. I've yet to see any good piece of code which does path following robustly. There is a simple stupid case which is really hard to get right, that is, what to do when you encounter in-between path point?

Most code out there just checks if the character is close enough a path point and starts steering towards the next one. The problem is that depending how you generate the steering velocity, this can lead to circling around the path point or if you increase the threshold too much there is a shortcut.

I know quite a few games which have successfully shipped with the most awful path following code out there.

The most inspiring recent method to follow path can be found in Indicative Routes for Path Planning and Crowd Simulation. It feels a lot similar as the distance based GPU heightfield raycasting. While interesting, the method has one failure. In order not to shortcut, the radius of the agent should be reduced from the radius of K. Which in practice creates the silly singularity problem again.

The most simple and most robust path following code would of course just interpolate over the spline, but if you want to do some sort of local steering to avoid other moving agents that will not work anymore.

I don't know the perfect solution, but here's my current shot at it.


Global and Local Planning

I split the navigation into two problems, global navigation and local navigation. This is a common way to overcome the uncertain environment in for example robot navigation research.

The point of global navigation is to find a high level path to the target location. In practice when using navigation meshes this means finding the list of convex navigation polygons which will lead us to the target. I use A* for this search. The global navigation structure is static, but can change to reflect changes in the game world.



The second part is local navigation, it will execute the maneuvers to move the agent from the start location to the goal location via the path corridor.

Since I'm aiming to solve the navigation problem amongst multiple moving agents, I cannot use one shot shortest path generation since its' results will be invalid immediately when any other agent moves. For this reason, I do not find the full straight path spline to the goal. Even if straight path string pulling is really fast with Detour, finding the whole path would just was the processor time.

Instead, on every tick a character wants to move, only few next points (A and B in above picture) of the straight path are calculated. These few path points are used to calculate a velocity to steer the agent towards the target.

This method also ensures that if an agent overshoots to reach a path point, we still always get the shortest path towards the target and prevent silly things like trying to go back to a intermediate path path which we have actually already passed.

In order to avoid the singularity case when the agent is close to one of these path points, the point B is used when the character is really close to point A. This is not optimal, but currently I do not have really good alternative for this. With Detour this will not cut corners, though, because of the way the movement model along the navmesh works.

Moving Along a Path Corridor

The goal of the movement model along navmesh polygons is to move the agent through navigable space, or in case of collision slide along the navmesh boundaries.

In order to keep the whole system robust, the agents are kept and assumed to be inside the navigation mesh at all times. In practice this is not the case. When an agent is close to a polygon edge, floating point accuracy will make the agent to flicker in and out of the polygon boundaries.

The above picture illustrates a case where agent A is moving in the direction of the arrow towards T. Because the movement vector is colliding with a polygon edge, the target location projected on the polygon boundary so the it results sliding motion. There are several ways to do this.

A classic way to do it is to iteratively cast ray (or ellipsoid), clamp it based on the hit surface normal, until the movement is resolved. This method is quite hard to get robust because there are a lot of cases where you need to handle collision between parallel segments.

Since our movement model is supposed to travel inside convex volumes, we use a bit different and more robust method. The whole iterative ray-casting loop can be replaced by finding a closest point from the target location on the boundary of the polygon.

If you want sliding movement inside a convex polygon, that is all you need to do! While this may not be numerically most robust method, the logic to implement this method is robust. We simply move the agent and clamp it to the polygon boundaries. Even if the agent is slightly outside the polygon because of precision, it can be all the time treated to be inside.

This method can be extended to move along path corridor.

• We start from the current navigation polygon (PA), current location (A) and start moving towards the target location (T).
• If the target is inside the polygon, we set the current location to the target and we are done!
• In case the target is outside the polygon, the current location will become the target location clamped to the nearest point on the polygon boundary (B).
• If this clamped position is really close to the portal edge which leads to the next polygon (E), we move the current polygon the next one (PB).
• If the clamped position does not touch the portal edge, we cannot move know that we cannot move any closer to the target and we'll stop.
• This process is repeated until we either reach the target location or cannot move anymore.

The process may sound a bit backwards, but because the way it is implemented we can dodge a lot of robustness issues.

Towards Obstacle Avoidance

The way to extend this to obstacle avoidance is to adjust the velocity. First, the velocity towards the target is calculated as per above description, and then it is adjusted according to your favorite local avoidance method. For example the method described earlier in this blog could be used, finally the resulting velocity is used to calculate the next movement step.

Since the obstacle avoidance may sometimes need to deviate from the corridor, I expect that I need to revise the navmesh collision response at some point. Instead of allowing to move only to the next polygon along the path corridor, it should be possible to move to any neighbor polygon and just append or remove polygons in the beginning of the path. There are a couple of details still, which I have not solved, though.

_

I hope I did not skip too many details while writing this. I just got the last pieces together today while implementing this. The updated code can be found from the Recast SVN at google code. The path iterator can be found in Sample_SoloMesh.cpp, in toolRecalc() method, check the path find tool code. The Windows project is yet to be updated.

[EDIT] Visual studion and Win32 exe updated.

Zak Pak is a nice package

Recently I have played much more boardgames than computer games. Maybe the New Super Mario Wii is an exception. We got new game a little while ago called Zak Pak (Pack & Stack).

I was immediately attacted to the wooden pieces and the nice graphics of the game. Some board game sites also seemed to like the game. After the first couple of rounds of the game with our good friends I felt not so compelled about the game anymore.

The biggest problem of that game is that it has many layers of randomness laid on top of each other. First you pick random pieces which you need to fit into a random truck. Surely the outcome is very random too.

The most stupid rule of the all is the way the trucks are picked up. First everyone picks up 2 truck cards (at random) and then all the truck cards are turned over at the same time. Then you choose one track that fits the best to your random piece set from the other person's truck cards. Fine, but then... the last person who picked up his truck must discard it and pick his/hers card at random from the truck card deck.

Since everyone was concentrating on picking up the best card from the deck, there is no time to be the referee to see who was the last person to pick up a card. This leads to a lot of frustration as people sort out who is the looser. And as an added bonus, the game is scored by penalty too.

So there are some stupid little rules which make this game to have bad frustration. Playing a hard level on Super Mario is good frustration, makes you try harder!

The reason I recommend this game to everyone interested in game design is that it screams to be redesigned. Everything that comes with the game is gorgeous, the cards, the pieces and the dice. It is just the rules that suck :)

So the second time we played the game we tried our own variation, which is quite different. There are bunch of rule variations at the BoardgameGeek website too. Our rules were as follows:

Pakkaa & Stakkaa


PREPARATIONS

Separate the 4 high trucks from the deck, shuffle them and put them on the table in a row. Shuffle the rest of the truck cards and place them into a pile on the table. Each player turns one truck card from the pile and gets 25 worth of money. The game is about to begin.

EACH TURN

Loading: In the beginning of a turn a player rolls the dice and picks up pieces accordingly. The pieces are loaded into the truck until it is full or no piece fits anymore. The pieces that were placed on last round cannot be moved anymore.

At any time during his turn the player can purchase one extra car slot for 50 pieces of money. The player can draw the new truck immediately after the purchase. If the player runs out of money the extra car slot can be sold for 25 pieces of money. The extra car slot allows the player to keep 2 trucks on the table all the time.

As long as some are available, the player is also able to purchase any of 4 high special trucks for 20 pieces of money. The special trucks are for one time use only, once they are full and cashed, the truck is gone. The special trucks have a little bit of different scoring.

Scoring: At the end of each turn, excess cargo pieces will be penalized and fully loaded trucks can be cashed.

Per each cube that is left out of the load the player has to pay two penalty points. The excess pieces are returned to the piece pile.

If a truck is fully loaded, the player gets one piece of money per each cube (1x1 piece) of the load. After that the pieces are returned to the piece pile and the truck card is put on discard pile and the player draws a new card from the truck pile to replace it.

The truck that is being cashed is a special 4 high truck, first the dark blue dice is rolled. If the result is blank, the player gets no money from any of the cargo, but gets a new extra truck to replace the old one. Of the result of the roll was 1, the player gets the price normal 1 money per 1 cube, but if the result was 2, the player gets 2 money per 1 cube.

END

The game ends on the round where the last truck card is drawn. Unfinished trucks are discarded. Points are counted and the winner is the one who has the most points.

The result was not an awesome game, but it was a lot of fun to come up with the rules and iterate few rounds. Initially we allowed for example to overload the truck and used similar dice rolling to score that truck, but it did not quite work that well.

The extra car slot worked better than I expected. In the first half of the game, the players tend not to get any penalty points at all, but on the latter half it gets more dramatic.

For a two player game the pieces never ran out, even if I feared that that might be the case. It usually takes about two rounds to fill one truck.

Currently our game feels a bit too solitaire. For the next session I want to try out some rule to exchange the excess pieces. Maybe trading them, or come up with some other action that allows to to help or mess up other people's trucks.

Anyways, I recommend Zak Pak, not because it is good game, but because it can be a good game design exercise. If you have your own version of Zak Pak, please share it!