Algorithm for Sorting objects by proximity, influenced by RA

[rogerg (Roger)]

Does anyone know of an algorithm that will sequence objects by proximity, minimising slew distance while still ensuring the complete set is traversed with a preference to moving in DEC then RA such that objects are observed nearest the zenith and definitely observed before they reach a western limit?

I have flashes of memories going through my mind of tree/node traversal algorithsm from university with branch distanced involved but haven't really dealt with them since so I'd be going back to a couple of text books and stating from there.

I'd like to take a set of n objects and sequence them in such a way that my slews are minimal (allowing most chance of an accurate plate solve), but such that I'm still working through in a way that I get them imaged before they go too far west in the night.

In TheSky it's very easy to retreive a set of objects filtered on suitable criteria and sequence them based on many attributes including RA and DEC, but I would prefer to be sequencing them on RA, influenced by their relative DEC positions.

Too much? too heavy? sorry! I doubt I'll get any replies to such a wacky questions anyhow..

Once finding an algorithm I'm expecting I'll have to knock up a little application to read in a CSV, do the sorting, then write out a new CSV, unless a miracle happens and there's software out there to do this, that us amateurs know of?



Thanks,
Roger.

[sheeny (Al)]

G'Day Roger,

I don't know of any ready made algorithms that would do what you want, but my approach would be to do something like this:
1. export a list of targets for the night;
2. group them by RA hour or half hour;
3. starting at the western most RA group, sort them by dec - ascending;
4. for the next RA group, sort them by dec - decending;
5. alternate ascending and descending sorting with each RA group.

The width of the RA group (1 hour or 1/2 hour, etc) depends on how many objects you have in each group. As 1 hour of RA equals 15°, if you start with 1 hour groups and find you have more than about 10 objects in the group then you'll be doing more slewing in RA than dec, so use a smaller RA group. At 1/2 hour RA group width, you can have about 20 objects in the group before the cumulative RA movements are more than the dec movements.

Al.

[sheeny (Al)]

If you're looking at what I wrote (above) and wondering what maths I used the logic was as follows:

1 hour = 15°.
The range of declinations = 90°+90°- your latitude (which I assumed to be 30° roughly) = 150°.
So, if more than 10 objects in a group the dec movements will be <15° on average.

hmmm... you could probably also argue that the average movement in RA will not be 1 hour (15°) but probably 7.5°, so maybe we could allow 20 objects in a 1 hour RA group and 40 in a 1/2 hour RA group.

But anyway, it should get you started, and you could do it in Excel...

Al.

[rogerg (Roger)]

Excellent aproach to take, that'll get me started for sure. Very different to what I was imagining but will work much easier I think.

[ausmensan (Simon)]

Hi Roger,

An interesting article, which I think relates to your problem:

http://grids.ucs.indiana.edu/courses...rch%201997.htm

I couldn't see any actual algorithm there, but perhaps it may be of some help.

Cheers

[gary]

Originally Posted by ausmensan

Hi Roger,

An interesting article, which I think relates to your problem:

http://grids.ucs.indiana.edu/courses...rch%201997.htm

I couldn't see any actual algorithm there, but perhaps it may be of some help.

Cheers

Hi Simon,

Indeed, in is purest theoretial form, determining a precisely optimal path in this
type of problem is what computer scientists refer to as "NP complete".
NP means "Non deterministic Polynomial time" and the "complete" part basically
means "forget about finding a solution anytime soon".

One of the most famous problems in this area is the Traveling Salesman
problem, which your cited article references. A seemingly simple problem,
yet it is defined as being "NP-hard". Some of the brightest minds in mathematics
and computing have worked on it and about seven years ago, some researchers
made some in-roads into it with some new algorithms.

Simulated annealing is a powerful technique used in a variety of disciplines
these days. In the mid-80's I first heard of it from colleagues I was working
with at UNSW who were using it to help route very large scale
integrated circuits.

Though well beyond what Roger would want to do or even need to do
in any practical terms, let alone put in an Excel spreadsheet, it is interesting
to read how techniques such as simulated annealing are still be used today
to find near-optimal solutions to what end up being very complex problems
otherwise.

Thanks for the article reference which is a good read.

Best regards

Gary

[ausmensan (Simon)]

Hi Gary,

Nice response, thanks for the detail! I came across simulated annealing when working on a neural net project a decade ago. I also understand that the NASA considered using such strategies in dealing with Hubbles observation strategies.

Yep, overly complex for Rogers purposes, but interesting nonetheless!

Best Regards

Simon

[rogerg (Roger)]

Very interesting stuff I haven't had a full read of it all, but remember those things coming up in my university courses (Computer & Maths Sci.), and being very interested in them but not managing to hang on to the understanding long! (can be heavy stuff, as suggested here)

[peter_4059 (Peter)]

Have you had a look at Astroplanner? I think it might do what you want. There is a free version and a registered version. It has a sort function "Object - Minimum Slew Order" You can also sort by RA then by Dec in the registered version.
http://www.ilangainc.com/astroplanner/