• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Sign up now

# Something to get the mental juices flowing (an exercise in AI)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

11 replies to this topic

### #1TANSTAAFL  Moderators

Posted 21 September 1999 - 06:05 PM

ok. lately, i've been reading a book... "Artificial Intelligence: A Modern Approach", which i have found so far excellent.

anyway, while reading it, i came up with what i think is an interesting problem. i thought i'd share it with the group, and see what kind of ideas for how to implement such a scenario people came up with.

for simplicity, it deals with a 2 dimensional universe, with no gravity, no friction, but the usual laws of inertia apply. there is mass, length, and time, and the units we will use for them are Kilogram, meter, and second, although these are completely arbitrary names merely used for convention. we shall say that one frame=one second.

there are some objects in this universe.

each object has the following properties:

mass(remains constant for individual objects)
velocity(direction+speed)
acceleration(includes a direction)
position(an x,y coordinate)
spin(change in direction/second, measured in degrees)
torq(change in spin/second)

there are 3 such objects in this universe...

object#1: the Chunk.
this is a chunk of rock, but could be any piece of floating debris.
the chunk has spin(randomly set at the start of the simulation), velocity(also randomly set), a mass of 1000kg. it cannot accelerate or apply torque to itself on its own.

object#2: the Collector
this is essentially a bucket into which the chunk must be placed. for all intents and purposes it is stationary.(however, it MAY have a random spin and velocity). like the chunk, it cannot accelerate or torque itself. the mass is immaterial, but for sake of consistency, it masses 2000kg.

object#3: the TugBoat
the tugboat is the focus of this exercise, since it is the only agent that can perform actions. it masses 250kg. it starts at the same position as the collector, with the same velocity and spin as the collector(if any), and it has its landing claw on.

the landing claw of the tug will attach it to another object, thus allowing the tug to apply acceleration and torque to the object to which it is attached.

the landing claw can only be engaged(turned on) when the position and velocity of the tug and the object to which it is attaching are equal. also, the spin of both objects must be equal. the tug can only attach to one object at any time.

besides the landing claw, the tug has 4 other ways to affect its environment. these work in sets of two.

thrusters:
there are foreward and reverse thrusters. they accelerate the tug(and any attached object) in the direction in which the tug is facing, or the opposite direction, respectively. only one will fire at any time, and we represent 1 as being full forward, 0 as both off, and -1 as being full reverse.

the amount of force exerted by either thruster is 250 kg-m/s/s. this means (for the physics impaired), that it can accerate itself alone at 1 m/s/s. but if it had the chunk attached(making it a total mass of 1250, it would only accelerate (250 kg-m/s/s) / (1250 kg)= 0.2 m/s/s.

turning thrusters:
the tug also has two turning thrusters. a clockwise(starboard or right) and a counterclockwise(port or left). 1 represents pure clockwise turning, -1 pure counter clockwise turning, and 0 means no turning.

these apply torque to the tug and any attached object.

the amount of torque is 2500 kg-degrees/s/s. this means that the tug can torque itself by 10 degrees/s/s, but if it had the chunk attached, this would drop down to 2 degree/s/s.

sensors:
the tug has a number of sensors it can use to help with its task.

distance sensor:
the tug can look at any other objects and tell how far away it is from itself.

relative bearing sensor:
the tug can look at any other objects and tell which direction it lies, in relation to the tugs own direction... for example, if the tug was facing due west, and another object was due north of it, the tug would see it as 90 degrees clockwise from itself (i.e. 3o'clock)

relative spin sensor:
the tug can detect how fast another object is spinning. this sensor can only be used when the position and velocity of it and the object it is observing matches exactly.(i.e. the tug and the object must share the same axis of rotation) note: if the tug is currently rotating at 10 degrees/second, and the object it is observing is rotating at 15 degrees per second, it would see the object as rotating at 5 degrees per second.

now that we have laid out the rules, we can now state the goal of the scenario...

its simple: get the chunk to the collector, and make sure their spins match. when this occurs, the collector will automatically assimilate the chunk, making it a larger collector. then the tug must dock with the collector.

collision does not exist in this universe.

if there are any questions for clarification on this problem, just ask.

### #2TANSTAAFL  Moderators

Posted 13 September 1999 - 07:04 AM

oooh... forgot one thing...

for some reason or another, the collector should not be moved...

### #3felisandria  Members

Posted 13 September 1999 - 09:16 AM

Assuming the stated 2D universe, it follows that the axis of spins of all objects must be perpendicular to the plane of the universe, assuming of course that none of the objects are lines or line segments. This would indicate the necessity of making the tug orbit the chunk in order to make the connection (ooh, evil problem)... unless we can place the tug "over" the chunk due to the statement that collision cannot occur? (in which case this wouldn't be a true 2D universe, but oh well...)

-fel

### #4TANSTAAFL  Moderators

Posted 13 September 1999 - 09:50 AM

there is no collision problem. we assume that objects with mass take a ghost form, or are all in one infinitesimal point.

if you like, consider that the tug, the chunk, and the collector exist in different parallel planes of 2d space, with the chunk in the plane below the tug, and the collector in the plane below the chunk. the landing claw can reach between these planes, and the collector can reach up one plane to assimilate the chunk.

(in reality, this would normally be a 3d problem, and the positioning would be over the rotational axis of the chunk, but i made it 2d to simplify it, because we would otherwise need to take into account roll and pitch instead of just yaw)

[This message has been edited by TANSTAAFL (edited September 13, 1999).]

### #5felisandria  Members

Posted 14 September 1999 - 07:25 AM

Is the tug capable of determining its spin relative to the "universe"?

### #6TANSTAAFL  Moderators

Posted 14 September 1999 - 09:10 AM

at first, i was going to disallow the tug knowing its own spin, but i came up with the design of a device that could do it(pretty simply, too)

so we will add a sensor to the tug. it can sense its own exact spin.

### #7felisandria  Members

Posted 14 September 1999 - 09:53 AM

Secondary goal of exercise is:
- Conservation of fuel
- Speed of retrieval
- Shortest distance
- I don't care, just get the stupid rock
...?

*smile*
- fel

### #8TANSTAAFL  Moderators

Posted 14 September 1999 - 11:58 AM

for now, we just want to get the stupid rock(teaching the tug to do just this by itself is a complicated task)

fuel is not currently a consideration, although if we solve this problem as is, then we can add in fuel considerations later.

efficiency is a good secondary goal, although there is no time limit currently.

in other words, there is no path cost to consider, but we really dont want to be sloppy about it.
------------------------------------------

some of my own thoughts on this so far.

step 1: detach from the collector
step 2: match velocity with the chunk
step 3: match position with the chunk
step 4: match spin with the chunk
step 5: attach to the chunk
step 6: match velocity with the collector
step 7: match position with the collector
step 8: match spin with the collector
step 9: detach from the chunk(thus allowing collector to assimilate it)
step 10: reattach to the collector

of course, these 10 steps are highly abstracted, and quite far away from "turn on forward thrusters to 45%" and "turn on starboard turning thruster to 96%", which is the level we have to get down to in order to teach the tug to fetch the rock.

### #9felisandria  Members

Posted 14 September 1999 - 12:23 PM

I'll just grab your steps and add...

step 1: detach from the collector
might want to despin here a bit depending on initial spin velocity

step 2: match velocity with the chunk
don't see how this would work... how would you catch up, especially if it's heading straight away from you as fast as it can? maybe match position first
step 3: match position with the chunk

I would replace 2 and 3 with:
- Locate chunk
- Begin acceleration toward the chunk
- Every interval, calculate distance from chunk and distance from collector. When at half with compensation for velocity of the chunk, start to decelerate. The "halfway" rule is the best in terms of getting there the fastest.
- Every interval, turn toward the chunk if you aren't already facing it. Granted your path will probably wind up parabolic and probably a bit wriggly, but we aren't being retentive about that yet are we? When we get that far we can start using control engineering feedback principles to make this more precise.
- When at chunk, you should be at the velocity of the chunk anyway due to the way acceleration was done, so continue with step 4

step 4: match spin with the chunk
step 5: attach to the chunk

I would probably just repeat the way we got to the chunk to get to the collector, go to step 8.

step 6: match velocity with the collector
step 7: match position with the collector

step 8: match spin with the collector
step 9: detach from the chunk(thus allowing collector to assimilate it)
step 10: reattach to the collector

Thoughts?

-fel
~ some people have an inner child. i have an inner electrical engineer with control engineering training and you just woke her up, darnit TAN... *grin* ~

### #10TANSTAAFL  Moderators

Posted 14 September 1999 - 02:21 PM

i would still keep my step2 and step3 as they currently are, and here's why:

while the tug cannot directly measure the absolute position or absolute velocity of anything, including itself, she(this is a spacegoing vessel, and therefore a "she") CAN determine the relative positions/velocities by figuring out an arbitrary coordinate system.

at Time=0, the tug is latched to the collector, thus moving with the collector and spinning with the collector. at this point, she knows nothing about the universe, so she has to make certain assumptions:

A: she is currently at her "home base", so she might as well call this position(0,0)
B: she has no sense of absolute direction, any direction will do as a reference, so she calls the direction that she is facing "north" (since she can tell how fast she is spinning, she can determine her "absolute" bearing in the future)
C: since she is latched, she knows that at time=1 that she will still be at (0,0), her velocity is 0, and she is not accelerating, so that will not change.
D: she can sense how far away and in what direction relative to her the chunk lies. she is facing "north" at this moment, so she also knows the chunk's position in her coordinate system.

during time=0, she should perform the single action of disengaging the landing claw.

next, during time=1, she has not moved relative to the collector, so is still at (0,0). she may have spun since time=0, but since she can detect her own spin, she knows what direction she is pointing relative to "north", and thus can translate any relative direction in terms of "north"

again, she detects the distance and direction of the chunk, corrects the angle to make it relative to "north", and plots the new position of the chunk in her coordinate system. this allows her to calculate both the direction(relative to north) and speed in which the chunk is headed.

now, her temporary goal is to adjust her bearing to point the same direction as the the chunk's direction of movement.

so, she must go from her current spin and currnent heading to the chunks heading, and spin of zero.

she can do this a number of ways. if she detects that she is currently spinning, she can wait until she is close to the proper heading and then stop her spin, or she can stop her spin ASAP, and from there induce a small controlled spin to match the heading, or she can determine a "half way" point to do a powered spin, where she applies turning thrusters for half the time in one direction, and the opposite thruster for the other half.

once she is facing the proper direction(or the exact opposite direction, for that matter), she accelerates to match the velocity of the chunk.

once this is achieved, the distance from her to the chunk will remain constant over time, so she must now turn to face either directly towards or directly away from the chunk.

now she can do either a start pulse/stop pulse firing of the thrusters to match the position, or a halfway accel/neg accel powered flight to match position.

once positions are matched, she can then match spin rather easily.

the trip home is exactly the same, the only difference being that the thrusters/turning thrusters are less effective because of more mass.

### #11Dæmin  Members

Posted 16 September 1999 - 04:52 AM

This sortof reminds me of a game that I found not so long ago, it is called RobotBattle, and a few of you might've heard it before. Basically its a bunch of script controlled bots fighting it out on a 2d arena, they can tell their gun, radar and body bearning and the some other basic items like the scan distance of the last scanned object etc. theoretically you might be able to set up a quick experiment using this program to see which one of you's is more 'correct'.

Anyway the whole package, along with some extra info is located at: http://www.robotbattle.com

so yeah, try it.

------------------
-Dom:)
Visit - http://www.eisa.net.au/~sdgrab/contents.html

### #12Turtle  Members

Posted 21 September 1999 - 06:05 PM

What about the position the claw is attached to, if the claw is attached to the exact center on the collecter, and the exact center, of the chunk, it might work with your steps, but if the claw is attached off center, you will have some very messed up velocities,spins, and directions when it is released. Example: sandwich a golf ball between two frisbees and throw them. note what ball does when they separate. Same will happen with your tugboat. The instant it releases. it will be going in a straight line and its spin will be completely nullified.

This adds the concept of release time.

Step 1: sense where chunk is at times 1, 2, and 3
step 2: calculate where chunk will be at time X where X is a reasonable time based on its distance and heading.
Step 3: Calculate the time you must release claw to propell yourself towards this point.
Step 5: release claw at correct moment
Step 6: apply thrusters to modify direction such as to reach this point at the same time as chunk (at every time increment till chunk is reached
Step 7: when chunk is reached, attach to edge such that, forward/reverse thrusters are perpendicular to the line that passes through the center of mass of the the chunk (diameter if circular) at its furthest point from the center of mass. And side thrusters are along said line. This should make your forward and reverse thrusters be able to change the spin without causing changes to velocity, and your side thrusters to be able to change the velocity without changing the spin.
Step 8: remove spin , and turn chunk such that the center of mass, tugboats, side thrusters, and the collector are all in a straight line.
Step 9: accelerate till halfway from first point at which you moved towards the collecter till you reach the halfway point
( this removes the problem with reaching halway at a huge speed due to the fact you started moving towards it at further away than you started accelerating(movement of chunk away from collecter)). Then start to accelerate in the opposite direction till you reach a standstill at the point of the collecter
NOTE: cannot spin chunk from edge to match spin with the collecter, because the instant released it would change the spin of the chunk and fling the tugboat away again.
Step 10: release chunk, and reattach at the center of mass of the chunk
Step 11: spin chunk till it reaches spin of the collecter
Step 12: release chunk
Step 13: attach to the collecter

I think I stated the steps needed correctly?

------------------
Tell the truth and you will never fear someone will figure out you lied.
<<I'm sure I'm quoting someone out there, wish I knew who!>>
David Abresch

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.