I made a little test the other day to see what is actually the difference between sharp (geometric) and smooth (sampling) velocity obstacle. The first segment shows hard boundary and the second shows soft boundary.
The code in both cases are the same, but in the first case, the time of collision is threshold to imitate geometric solution to velocity obstacles. If time to collision is < 1.5 seconds, then full collision penalty is applied to the sample, else no collision penalty is added.
In the second case, the collision penalty is inversely proportional to time of collision, making the velocity obstacle to appear softer. Even in cases where the geometric method would totally block the movement, the smooth boundary allows to find the best movement direction.
There are some twitching and bugs in the first segment when the velocity obstacle completely covers the sampling area.
—
On another note, Phil's comment on the one of my previous posts put me thinking. I think he's right. Obstacle avoidance alone will not create believable locomotion. There are a lot of nuances which can be only captured in the simulation if you simulate the perception, social forces, etc.
Instead of turning this project into a behavior simulation project, I will narrow my focus even more. It is such a monster research field already. I don't think an individual can successfully research and get something done in the human/crowd behavior simulation stuff in reasonable time.
Multi-agent obstacle avoidance is one of the sub-problems, and I'm going to focus on just that. I can later build some behavior stuff on top of this research if I choose so. Actually acknowledging that there is some higher logic above the obstacle avoidance, allows me to leave some things unsolved and expose them as parameters of the model.
For example if the agent always chooses the fastest possible speed, the result is rush or panic like behavior. If you always choose the nearest speed towards your target, the agent appears shy, or stubborn.
Even if I felt a bit despaired the week following Phil's post, I think it has really helped me to define the problem I'm trying to solve more clearly. Sometimes, it is actually harder to find the problem than to solve it.
Well the problem with perfect obstacle avoidance is that it's very specific to what or who is trying to avoid an obstacle. Humans would behave differently than say a cow, or a truck.
ReplyDeleteSo I think that this problem needs to be subdivided into chunks and solved individually, your work being an invaluable piece of the puzzle IMHO. (so please don't stop!)
Hey Mikko! I didnt mean to depress you, honest!
ReplyDeleteI guess the issue is that local steering looks really convincing for stuff like flights of birds, fish, buffalo etc. My educated guess is that these animals generally have a very low sense of self-urgency. Essentially they are almost entirely reactive, whereas humans are actually a lot more self-aware in comparison.
But the fun thing is that we tend to lose some of that in certain situations (dense crowds for example). So I think steering like this still has value, but for a crowd there are lots of things to take into account and as you say, its a BIG area.
I think even a really simplistic personality model would be useful, I've got a student working on such a beast, so hopefully we'll see if that pays off.
Anyway, see you in Paris!
Phil.
Mikko,
ReplyDeletePhil has a secret masterplan to depress you and make you less productive so the rest of us can look normal in comparison. If you bounce back so quickly he'll throw a different problem at you ;-)
Alex
Phil, it was politely defended point of view. I think it just resonated with some doubt I had. It turned out for the better, so no problem! Thanks, actually ;)
ReplyDeleteI wonder if there is any research on the differences between animal and human "locomotion". One thing that is common, is anticipation to avoid others. Maybe that recent IRISA paper [1] has some pointers. Too bad those biology/psychology papers are impossible to find for free.
There is this well known predator movement pattern where they try to look like they are moving parallel to the prey so that they can get as close as possible. I'm sure anticipation to avoid others is even more primal.
Anyways, it would be interesting to figure out the components that are needed for movement simulation.
[1] http://www.irisa.fr/bunraku/Julien.Pettre/dataset1.html
This comment has been removed by a blog administrator.
ReplyDeleteThis is an interesting thread, and one on which I have definite opinions. Collision avoidance is one of those commonsensical patterns of behavior, without which, nothing else works, and you can have all of the smarts on top of it and if the collision avoidance doesn't obey commonsense expectations, the resulting behavior is going to look screwy.
ReplyDeleteBut because it incorporates so much common sense knowledge about how the individual's body works, and the behavior of others, it is really, really, really hard.
So until we have commonsensical collision avoidance, FULL SPEED AHEAD!!!!
Of course, patterns of movement through space and time are highly species and context dependent. Think of how differently a rat and a dog might traverse/explore a novel space. The rat will tend to be out and back, out and back, slowly expanding its comfortable space, and will in any event tend to keep to the edges and shadows of the space. A dog will be very different.
I would take issue with the notion that animal movement is largely reactive and human motion is somehow more intentional. But that is a discussion over more than 1 beer.
That said, I am convinced that all behavior, be it animals or humans occurs within an emotional context, even if the dimensions of that context are very minimal (e.g., a 1 dimensional space going from shy to bold), so I do think at some level one needs to have some simple, and I do mean simple model, of emotion/affect.
But too, at the end if the day what matters is what story does the observer tell when watching our characters move, and what we really need to focus on is what we do to ensure that the story is consistent with our intent.
-bruce
I totally agree that some kind of behavior plays a huge role in that whole human motion modeling.
ReplyDeleteI also think that one common (low level) piece of that puzzle amongst most living things is anticipating opponents movement and adjusting your movement based on that.
I have tried to focus my current research to only deal with that on low level piece, and it seems to be a giant spaghetti monster of a research on it's own!
I think there are different ways to look at the behavioral level. On one end you can look at it how "real" humans would behave in "real" situations.
Another point of view could be, how would an actor behave in a well rehearsed situation? I think this point of view might be more well suited for game AI, and hopefully far simpler and more straight forward goal to reach too.
I think we expect "professional AI actors" in most of our games. Then there are the "reality show AIs" such as Sims characters which will benefit a lot from more more deep and emergent movement modeling.
I am apt to agree with you that focusing on the desired observable (which is what an actor does after all) is a good approach sitting on top of robust collision avoidance.
ReplyDeleteI agree too that we all want nice clean layers, but intelligence in nature doesn't decompose into nice clean layers, and I wonder whether we cause ourselves more trouble than it is worth trying to have these clean architectures.
The approach we took on World of Zoo was to give just enough scaffolding in terms of the animals' behavior that it was easy for the player, given the context in which the behavior was occurring, to make up their own stories as to what was going on. After all, in the absence of context, there are at most a handful of affective states that we can recognize, so why spend a lot of time and energy modeling more sophisticated states when in fact they may not be read by the player anyway? But I do think there may be a place for some really, really small set of affective states.
I don't see this field as nicely cut layers of cake, it is more like that suitcase plastered with stickers. You can still sort of all the pieces it consists off, but no two travelers suitcases (=implementatios) are the same. I'm working on one of those stickers.
ReplyDeleteOne reason I'm trying to focus my research really narrowly is also that I want to get as deep as possible understanding of the velocity planning/avoidance sub-problem.
For example looking at Alex's recent locomotion article [1], I immediately got bunch of ideas how to fit local avoidance logic in there.
I think a lot of AI theory has similar trait as art theory (say color theory for example). You have a set of rules, which you can use learn the structure how things work, but in the end, it is all subjective and you can always find something that looks awesome but is breaking the rules.
I also wish to produce some material which will help other people to get a tiny notch further in terms of quality when they are building games. Navigation and locomotion are both really complicated issues, and I hope that my work can be basis for others to implement more elaborate versions, or it could be used as is by some games.
[1] http://aigamedev.com/insider/reviews/holy-grail-locomotion/
Just to be clear, I think what you are doing is exactly the right thing, and I am really glad you are doing it.
ReplyDeleteOne of the interesting things about the brain is that we often think of the brain as being hierarchically organized with forward projections from lower portions of the brain (e.g., the visual cortex) to 'higher' portions of the brain (e.g., specialized modules that extract motion, faces, what, where etc...). The interesting thing is that there are more back-projections than there are forward projections. That is, perception is neither Top Down nor Bottom-Up, but Bottom-Up and Top-Down working in concert, each facilitating the other. Shimon Ullman is the one who pioneered this way of thinking about the brain.
Anyway, it is an interesting model to think about.
Mikko, could you send me your email address. My email address is bruce_blumberg@me.com
This might be related, or totally different thing...
ReplyDeleteOne thing that I played around with my adaptive velocity selection was memory.
Basically I biased the velocity selection towards the previously selected velocity.
If you do this with single sample, that is, you sample really densely (say 80x80), and favor velocities close to previous velocity (in addition to the other weights), then you get too stubborn results.
But if you use hierarchical selection, like my adaptive method is, and apply strong bias in early coarse levels of the hierarchy and loosen it later on, you can get rid of some of the spikes in the velocity selection, but the results can adapt really quickly.
That would be quite close how dopamine work, I guess.
Not sure if that hierarchical method is bottom up or down. Maybe having bias per level would be even more interesting.
Also another brain related pondering from recent past is, whether our movement prediction comes from the reptilian brain, or if it is the work of mirror neutrons for example.