# AI for Space Nav computer

This topic is 4676 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Heres something to think about. (just a challange). You have one camera, that is looking strait ahead. From that, and a star map, work out where you are, your direction and heading. (given that you can use multiple frames). Star map, can be abything you want. As long as it is smaller then 500Mb, and you don't use a large amount of processing power when computing your position. (large, as in, you have maybe a second to come back with your answer. On a 1ghz arm). let the thinking Begin! From, Nice coder

##### Share on other sites
As a second task: Make a path from two points, which would use the least energy. (ie. No going from gravity well to gravity well, ect.) and use your cource information to follow it well.

From,
Nice coder

##### Share on other sites

Sounds nice an vague/incomplete -- kind of like 'ideas' that marketing people usually give.

Star Map data can be anything I want ??

OK my map data has spectrum frequencies accurate enuf to be able to discern each star uniquely and the 'camera' can register that info.

I was gonna say my map has 1 star on it, but that would have been too easy.

You need to be a bit more specific (and clear) in your 'challenges'.

##### Share on other sites
Ok.

Challange 1:

Determine velocity, position and orientation, from a continuous series of images ftaken from the front of your spacecraft.

Challange 2:

Create a path from two points, using the lowest amount of thrust.

Challange 3:
Use the first two challanges to develop an algorithm that will stick to the path.

All chalanges are to be done on a memory budget of 500mb, and a processing budget of 1 sec on a 1ghz arm processor.

From,
Nice coder

##### Share on other sites
The under 1 second bit is a killer.

My star map contains sets of statistically unique star combinations used for navigational aid.

i.e. A set of stars that form a 3-D 'Cross' in space, (-X-), a cluster of stars that differ in magnitude in a 'binary' style (bright, dim, bright, dim), a set of stars that radiate at unique wavelengths, a set of pulsars and their periods, etc...

Lets just say I have 300 different 'fingerprints' to look for. All I need to do is identify three of them to determine where I am.

Images taken using my camera get converted in to a series of vectors, where each star gets represented as a list of normalized vectors to the other stars in the field of view.

I could probably then compare the normalized vectors to the features in my star map.

Will

##### Share on other sites
You still have one billion ops for searching.

What would happen if the time limit was raised, to say.... 5 secs?

What i would do, is splat every star onto a sphere that is about the orbit of pluto. (a bit over that).

Without any planets, of cource.

Now, for every star, i remove those that are too similar in colour and position so that i couldn't be seeing two of the same stars.

Now, once that is done, i simply do some image processing to find the intensities and relitive positions of all the stars, before processing it into a set of numbers, and searching the databank for them.

Once i find a few stars, i take the angle that i am with them. (basically where they are in the picture dictates where it is as an angle to where i am going), then from that, and there positions i triangulate my position. (i know where they are (in the sphere), and i have the angle between them and me, and i have heaps of them, so i should be able to work out my position quickly).

I ignore any stars that i do not know.

I do this with a few hundred stars to accurity figure out my position to within a few meters.

Once i have that, i take another photograph, and compare the two positions, and from the two positions and the time between them, i work out my velocity vector.

I can also work out spin, ect. By where they are rotationally.

From,
Nice coder

##### Share on other sites
Nice Coder:

The way we solve this problem with telescopes (of the backyard variety) is to calibrate an instrument (like a camera on a mount) against a know set of stars (Polaris, Alderbaran, etc..) and the time. If you know the time of day (GMT) and can tell the telescope what it's pointed at, you can know exactly where you are and exactly what your heading is at all times.

I imagine you could do the same thing with the space ship.

##### Share on other sites
It's not such a simple problem as it sounds (and in fact is an active research topic).

Consider this scenario:

You have a database of constellations, which are projections of sets of points in space onto a plane surface of finite size. We have a (roughly) fixed set of constellations on Earth because the great distances to the stars in the constellations means motion effects translate into almost insignificant angular displacements.

Now, the problem faced by the Nav Computer is that it needs to consider an infinite number of possible plane surfaces, one for each possible camera position it could have within the known space. What this equates to is the ability to look at a star field captured by the camera and determine the transformation required to have it match exactly one constellation in the data base. This can be done using Bayesian techniques, although computationally you're not likely to achieve it within 1 second on a 1GHz machine.

The other solution method is to solve the inverse problem: given a 2D projection of a set of points embedded in 3D space, determine the most likely 3D embedding. Clearly though, this problem is under-determined unless you impose further constraints. Typical constraints are to assume the same luminosity of sources, so that luminosity differences in the camera image can be attributed to distance. You're in trouble though if there is intervening dust that decreases luminosity in the image. Basically, unless many over-simplifying assumptions are made, this method isn't practical.

The third idea would be to use triangulation methods, however given the distances to stars in space relative the the distances spacecraft can travel (even at light speed), there would be large errors in triangulation estimates of position, due to the errors in estimation of angular change. One *might* be able to combine triangulation with the inverse problem to triangulate the relative position of stars.

The final method is to use parallax to estimate the distance to each star (for use in the inverse problem). The only problem here is that you need to assume an exactly known focal length of a lens and be able to measure extremely accurately the distance to the image from the lens.

Personally, I'd go with the first method, since it equates to the problem faced in current research of context sensitive image retrieval. A good example of this sort of problem is, given an MRI of a patients brain, find an MRI scan in a database of other patients that most closely matches this scan. You face the same transformation problems and the same inference problems as well, so I suggest you read up on the literature in this field if you're serious about finding a solution to your problem.

Cheers,

Timkin

##### Share on other sites
There are still a lot of unkowns, how far am I traveling for one?

Lets assume I'm just traveling in this solor system.

My star map consists of a SDSS(Sloan digital sky survey) on much smaller scale and a dsiplacemnt map of the solar system. The star map is updated periodically by an algorithim that use known data to calculate steller drift. The camera converts the image into a comparable format and uses the ships last known position to compare the camera image to the ships assumed posistion in the starmap and then determines the ships current position. A comparison with the last known posistion reveals speed, heading, and acceleration.

With the ships position detetermined, the course plotting algorthim uses the density map to plot the path of least resistance to the destination.

The ship follows the course by comparing its current position to its assumed position on the path and uses the ships thrusters to adjust velocity and heading when its current position deviates from the assumed position.

##### Share on other sites
1 or even 5 seconds is not sufficent time to calculate a flight path for a space ship, since you're forgetting a key factor in astronmoical travel and that is time. When you plot a course in space you plot the course not for where your destination is but where it will be when you arrive.

##### Share on other sites
ok. Heres my idea.

First you find all of the stars. (ie. do image processing to find each star from the image, then search a list which contains all of the distinguiahable stars).

From them, finnd the angles between you and all of them.

From that, triangulate your position using many thousands of angles.

Is ths a better way?

From,
NIce coder

##### Share on other sites
Quote:
 Original post by Nice CoderFirst you find all of the stars. (ie. do image processing to find each star from the image

How do you propose to do this? This is not a trivial problem unless each star happens to be a unique token within the image that can be readily identifiable. Star images are just a collection of pixels of varying intensities at various wavelengths. Let's assume for a moment that your camera was actually a spectrograph and it could accurately detect the frequency spectrum for each star. You still need to assume that every star has a unique spectrum, which is simply not the case in real universes. Indeed, stars within a class typically have very similar spectra. If your camera is simply a band-limited CCD, then you're in trouble!

I think most people are not considering the complexity of this aspect of the problem and are assuming that you can easily identify the stars in the picture.

Cheers,

Timkin

##### Share on other sites
agreed... it would be must easier if we knew our current location... is that allowed?

##### Share on other sites

So, if you had it, it would get rid of the problem, [lol]!

From,
Nice coder

##### Share on other sites
My five cents is that the problem itself may be unsolvable given the relative data you are given. Its like being dumped in the middle of the ocean and you have to somehow swim to shore when there are no sensible current, winds, and that the sky is cloudy to the point of no visibility.

Well, you might say that we have star charts, but those are practically useless due to certain visibility issues and the gravitation effects on light. Just the fact that gravity bends light makes it difficult to match anything, especially when you don't know what's bending the light coming from where. Not to mention different stars are visible in different locations in space with differring colors due to refractions etc.

Its a mental challenge alright. Just coming up with all the possible events that can prevent you from finding any sort of reference frame is challenging enough. :|

Its a nice mental exercise, but that is pretty much it. We're so used to navigating on earth where there are many visible and accessible frames of reference that navigating in deep space in uncharted territory will just be a huge leap of faith.

##### Share on other sites
assuming you are within a galaxy, can't you estimate the center of the galaxy from the sky pics? I mean the milky way is a bright band of stars that is recognizable. then you find the closest galaxy visible from your vicinity or perhaps black holes, neutron stars, quasars, anything rare enough to be a reference point. given you know the center of the galaxy and other galaxies visible from your location, can probably get your position. navigation would be simple since you have a map, you know where you are and where you are going.

##### Share on other sites
There would be certain things you could use to determine your general location.

The center of the galaxy is a very good idea.
Pulsars and binary star systems would be another.
Any 'unusual' stars.

The problem is solveable, but maybe not as Nice Coder presented it. You would have to take a series of images of a number of different sections of the sky, and some of the 'images' would be have to be taken outside of the visible wavelength, at different levels of magnification.

There would be places where knowing your position would be impossible (inside of a dust cloud, etc..)

##### Share on other sites
The catch is "visible."

What we deem as visible here, may be deemed "invisible." elsewhere in the universe. The problem does not specify where, so that raises the possibility of somewhere where our galaxy may not be visible. Thus, unless you have a "complete" map of the "entire" universe, you only have a probabilistic chance of being able to find your way.

Its kind of like trying to find your way in montana when you're given unlabeled local road maps from random places in the US. roadmaps may look similar, but without the proper labelling, you really have no clue if what you're looking at is really where you are.

##### Share on other sites
Stars are a bit to "common" to be usefull on determining your position.

I'd sooner say that I use galaxies.

I've heard that Andromeda can be more easily found.
I suppose you can use other galaxies to find your location (same as with a GPS).
Though not with a forward fixed camera (unless you have some kind of heading, which could be gotten through a gyroscope).

##### Share on other sites
Is it even possible?

     S  B  Y  R     S

S = Ship.
B, Y, R = Blue, Red, Yellow Stars.

Blue is on the right and Red is on the left of the top ship. Blue is on the left and Red is on the right of the bottom ship. Now if the bottom ship was upside-down, then it'd be backwards.

Obviously it'd have to be the EXACT same point on the opposite side, but would that not be impossible to detect?

##### Share on other sites
For those that are actually interested in how to solve this problem, you should consider the parralel problem known as localisation within the robotics community. However, it's easier for robots because we can mount range-finders onto the robot in addition to cameras. If you can solve the robot localisation problem with only a camera (which you can, but only probabilistically) then you can solve the celestial navigation problem using the same, or similar techniques.

Cheers,

Timkin

##### Share on other sites
I've changed my mind. I think the problem is impossible to solve.

Simple reason: no parallax.

Celestial bodies are so far apart that you could move thousands of kilometers without noticing any perceptiable difference in star / galaxy / whatever positions.

##### Share on other sites
Quote:
 Original post by RPGeezusI've changed my mind. I think the problem is impossible to solve.Simple reason: no parallax.

There is parallax, it's just a question of whether you have the ability to detect it (i.e., the sensitivity in your observation system).

Furthermore, solving this navigation problem would only be a problem when you had to travel out of your local region, which would only occur if you could travel at significant fractions of c, in which case it would be easier to detect parallax!

You do make a valid point though that the accuracy of your position estimate is highly dependent on the accuracy of your sensors. This is a well known fact in robotics!

Cheers,

Timkin

##### Share on other sites
Some thoughts:
If you know where you are now, if you check again in 5 minutes you don't have to start from scratch. You are within a certain radius of your last known position. If you've made no course corrections since your last known position then you can narrow it further(dependent upon how far you are from the nearest gravity well).

Your challenge sort of sounds like; you have a star map and you wake up on a spaceship somewhere in space, figure out where you are. That is a much greater challenge then simply tracking travel through space.

Some other ideas to simplify the equation:
Pick a "north star" Keep a guiding star on your nose throughout your journey. This way you always know that your ship is somewhere along a line between your north star and your starting position.

Landmarks Pick out unique objects in space to triangulate your position. Galaxies, pulsars(with specific rotational indices), binary star systems.

Signposts Deploy navigational buoys with unique signals

##### Share on other sites
Quote:
 Original post by Matt AppleSome thoughts:If you know where you are now, if you check again in 5 minutes you don't have to start from scratch. You are within a certain radius of your last known position. If you've made no course corrections since your last known position then you can narrow it further(dependent upon how far you are from the nearest gravity well).Signposts Deploy navigational buoys with unique signals

This is known as dead reckoning navigation, and was the primary method of finding a boats position before the advent of GPS. You can find your position from scratch using a sextant, as long as you have accurate time, (taking elevations from the sun, moon and known stars), but it is much easier if you know approximately where you are from your last position.

In space this would probably be much more accurate, as long as the local gravity fields and solar-winds are mapped, because there is no unpredictable current/weather to throw you off course.

Just though of another point: If you are travelling a relativistic speeds (near light-speed), what can be considered 'accurate' time, i.e. what time frame are you navigating relative to. Since the passage of time is affected by your speed.
And, for that matter, you can't just calculate your position from scratch, you must find your time as well, as the two are inter-related.

SwiftCoder