Sign in to follow this  
cache_hit

newton's laws of motions

Recommended Posts

This feels like an incredibly stupid question, but maybe I'm just having a brain fart. I have 2 entities, A and B. B is stationary, and A wishes to arrive at the B's location in some given amount of time. Naturally, it wants to decelerate as it nears B's location to give a smooth motion. my entity update function looks like this:
void entity::update(float dt)
{
	behavior_delta delta;
	behavior_delta result;

	//Combine all the forces into a net-sum force to be applied
	BOOST_FOREACH(behavior& b, behaviors_)
	{
		delta = b.execute(dt);
		result += delta;
	}

	//Update current pos/velocity using current velocity/acceleration
	pos_ += dt*velocity_;
	velocity_ += dt*acceleration_;

	//Save the new acceleration for use next time
	acceleration_ = result.accel;
}

And my execute() function of this particular behavior looks like this:
behavior_output behavior_arrive::execute(float dt)
{
	behavior_output delta;
	D3DXVECTOR2 target_vec = destination_.get_pos() - arriver_.get_pos();

	float dist = ::D3DXVec2Length(&target_vec);

	if (dist > 0.0f)
	{
		float speed = dist / ideal_time_;
		
		speed = std::min(speed, max_speed_);

		target_vec = (target_vec/dist) * speed;

		//The necessary acceleration is given by the difference in
		//The new velocity and the old velocity.
		delta.accel = target_vec - arriver_.get_velocity();
	}
	else
		delta.accel = 0.0f;

	return delta;
}

When I do this, the entity trying to arrive at the target's location "overshoots" for a fairly noticeable amount of time and then turns around. Can anyone shed some light on why it's overshooting the target? I could always just put in some special logic to say "if it's within distance x of the target abruptly change your velocity" but I'm not sure I want to do that before understanding why this is happening.

Share this post


Link to post
Share on other sites
vf = v0 + at

if you want to reach smoothly and stop in a point, vf = 0 then

-v0 = at or a = -v0 / t

Now if you use
d = v0t + 0.5 a t^2

You should know your starting position (say 300 units) and the time you want to use to arrive to your destination (say 3 secs). Replace them in 2 and then with the two equations you may easilly compute the acceleration and initial speed you will use for all the exercise.

I don't know if this is what you need.

Luck!
Guimo

Share this post


Link to post
Share on other sites
I was trying to do it by calculating each frame the desired *acceleration* to apply to the object. Physically I don't see why this shouldn't work. I changed it so that at each frame it calculates the velocity instead, and it just assigns the entities velocity directly instead of adding an acceleration to it.

It works now, but I'm not sure why the difference.

Share this post


Link to post
Share on other sites
I think the problem is that you want to reach the object with zero speed, it would take infinite time (if you use the force-acceleration). So you have to decelerate with lower value (lower braking force), so you will always reach the target with speed, that means it will overshoot.

I can recall a similar thread about it, the replies pointed to looking into PD, PI or PID controllers.

The point is that you can't design a controller (and your problem is a very typical controller situation), without overshooting, or never-reaching-the target situations (in theory).

image



So I guess the if velocity < v_tol and distance < d_tol then make position equal would work.

Share this post


Link to post
Share on other sites
I disagree with szecs on this one. You can't make a linear controller that arrives in finite time without over-shooting, but that's not the only type of controller you can build.

For instance, this code does the job:
#include <iostream>
#include <cmath>

double sign(double x) {
return x>0.0 ? 1.0 : x<0.0 ? -1.0 : 0.0;
}

int main() {
double position = -1.0;
double speed = 0.0;
const double dt = 0.01;

for (int i=0; i<205; ++i) {
// Try to stop in the next two steps
// Note: This computation depends on your integrator
double acceleration = -position/(dt*dt) - speed/dt;
double next_acceleration = -speed/dt - acceleration;

// If that requires too much acceleration, figure out which way we should accelerate
if (std::abs(acceleration)>1.0
|| std::abs(next_acceleration)>1.0)
acceleration = sign(-sign(speed)*speed*speed-2.0*position);

std::cout << position << ' ' << speed << ' ' << acceleration << '\n';
speed += acceleration * dt;
position += speed * dt;
}
}




EDIT: The code above is kludgy and doesn't work well in general, but it shows that stopping in finite time without overshooting is possible. I am working on a robust version.

[Edited by - alvaro on February 22, 2010 1:14:31 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I disagree with szecs on this one. You can't make a linear controller that arrives in finite time without over-shooting, but that's not the only type of controller you can build.


This is an interesting point. In fact, you can't use any continuously-differentiable (or more generally, locally Lipschitz) (even nonlinear!) controller to achieve finite-time stabilization. alvaro's works, for instance, because the sign function is not continuous.

That Lipschitz functions can't do this is easily shown; it comes from existence and uniqueness of solutions to ODEs (Picard's theorem). Basically, you know that for any state, you can simulate your system forwards or backwards to get a unique state trajectory for all time. But, since time is not part of your state, you can also translate a given solution forwards or backwards in time to get another function which also satisfies the ODE. You put those two things together with the requirement that the solution be zero for all t>T and you get a contradiction.

Share this post


Link to post
Share on other sites
Most of what you guys said lost me :) But, if I'm to take away one thing from this, is it correct to say that the reason it overshoots is because at any given time (including when you are arbitrarily close to the target) it is calculating the acceleration needed to reach that target in a certain amount of time, and as such even once you do reach the target your acceleration will be non-zero and thus you will continue moving?


I guess my next question is more about the design of such a controller framework. In general an entity has components such as position, velocity, acceleration, heading, and angular rotation. Maybe others but let's just use these as a starting point. In the example you gave above, the output of the controller is an acceleration to apply. Velocity and position are then integrated from acceleration. Other controllers might wish to output velocity directly, and only have position be integrated.

How should one deal with the fact that controllers can output values at various stages of the integration, and that they can be combined on top of that? If I combine 2 controllers that both output acceleration, it's easy to just add the accelerations, set the acceleration of the entity equal to the result, and then integrate velocity and position.

But if I have one controller outputting an acceleration, and one controller outputting a velocity, what does that even mean to combine them? Assuming that this even makes physical sense, let's assume I have two output structs:


struct acceleration_output { Vector3 new_accel; float new_alpha; };
struct velocity_output { Vector3 new_velocity; float new_omega; };



I then combine two controllers, one which returns a velocity_output and one which returns an acceleration_output.


acceleration_output output1 = controller1.execute();
velocity_output output2 = controller2.execute();

//Suppose I have class member variables pos_, velocity_, rotation_, omega_.
//What code follows to correctly update them in 1 iteration of an update loop?

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
Most of what you guys said lost me :) But, if I'm to take away one thing from this, is it correct to say that the reason it overshoots is because at any given time (including when you are arbitrarily close to the target) it is calculating the acceleration needed to reach that target in a certain amount of time, and as such even once you do reach the target your acceleration will be non-zero and thus you will continue moving?

No, I don't think that's correct. By the time you have reached the target your velocity will be non-zero and thus you will continue moving.

Quote:
[...]

How should one deal with the fact that controllers can output values at various stages of the integration, and that they can be combined on top of that?


You can make each controller simply add some contribution to the value that it modifies (acceleration or velocity).

acceleration = gravity + controller1.output() + controller2.output();
velocity += acceleration*dt + controller3.output();
position += velocity*dt;


I am not sure I can think of an example where this makes sense, but that's the first thing I would try if I had one.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this