Ask the Computer Scientist . . . (Help!)

[spacester]

Damn it Jim, I’m an Engineer, not a computer scientist!<br /><br />Some years ago, I got hooked on Orbital Mechanics. I studied the crap out of it and one conclusion was that there was no way for the non-expert to fool around with different scenarios for Interplanetary or even Cis-Lunar flights. It is possible, with a great deal of effort, to learn how to find the time of flight for a given transfer orbit given a certain deltaV.<br /><br />But in my mind, what is needed is the ability to work the problem the other way around: Given a time of flight (TOF), how much deltaV is needed? What are the options available to the would-be mission planner if all they really know is how long they want to take getting there? To this day, I find nothing on the web that lets a person do this.<br /><br />So I cooked up this computer program to calculate the transfer ellipse (the elliptical path) to go from any body orbiting the Sun to another. I have posted particular results here from time to time. <br /><br />(I also have issued appeals for help – to no avail - in moving the program from LISP for AutoCAD to something that could be distributed widely. In particular, I do not know how to create a Windows application which will graphically show what’s going on, something that AutoCAD does quite nicely and easily. I’ve pretty much given up on getting such help, but consider this paragraph one last attempt here . . .)<br /><br />I’ve been trying to tabulate the various solutions for <b>a wide range of flight times between Earth and Mars and back, for the years 2005 thru 2041.</b> (Because Mars’ orbit is very eccentric, there is a lot of strategy involved in choosing your flights, and I want to discuss the subject.) <br /><br />Doing this is a simple matter of automating the program to run repeatedly for these ranges, and saving the data for later tabulation and an <div class="Discussion_UserSignature"> </div>

 

[spacester]

On to the technical stuff and my appeal to the actual computer scientists here . . . <br /><br />A lot of stuff goes on in the program to do the whole job, but at the core of the calculation is an iterative solution that sometimes fails to work – it becomes an infinite loop. So I have had to identify those particular combinations of flight time and year that hang up and work around them. But even this approach is proving to be unworkable.<br /><br />I’m seeking a value of SLR (Semi-Latus-Rectum, a key parameter of the transfer ellipse) that will result in the requested TOF (Time Of Flight)<br /><br />I know that the sought-after SLR is less than SLR for Hohmann (SLR,h), which is easily found.<br /><br />So I set<br />Try = 0.99 * SLR,h<br />Then I find<br />TOF = a rather complicated function of SLR, not possible to be solved for SLR = f(TOF)<br />If <br />TOF, return value < TOF, desired value<br />Then <br />Increase SLR<br />Else<br />Decrease SLR<br />Repeat until <br />TOF, return value = TOF, desired value<br />To a certain number of decimal places<br /><br />As clunky as my routine is, it should work, but the problem is that AutoCAD has very poor calculation precision, and the core function has a lot of trig functions so the precision required is higher than what AutoCAD can produce. This is why it goes into an infinite loop. I have spent hours and hours tweaking the parameters – the SLR increment and the number of decimal places needed to be in agreement, but no one set of values works every time.<br /><br />So, my question is, my not being anything more than a brute-force programmer . . .<br /><br />Can someone show me how a real computer scientist would perform this iterative calculation so that it works every time?<br /><br />TIA<br /> <div class="Discussion_UserSignature"> </div>

 

[jcdenton]

<font color="yellow">As clunky as my routine is, it should work, but the problem is that AutoCAD has very poor calculation precision, and the core function has a lot of trig functions so the precision required is higher than what AutoCAD can produce.</font><br /><br />I'm not familiar with AutoCAD, but what's the precision required by your algorithm? Also, do you know any C/C++? If not I'd offer to help you out, if your programs are not too long. Those languages are best suited for programs with heavy computations.<br /><br /><font color="yellow">Can someone show me how a real computer scientist would perform this iterative calculation so that it works every time?</font><br /><br />You would want to have a break statement somewhere in your loop with the condition that if no further result that is closer to your expectations can be achieved, then break out of the loop. <div class="Discussion_UserSignature"> </div>

 

[spacester]

Hi jcdenton<br /><br />I have the barest knowledge of C/C++, just what I could learn in a few days of investigating it as an alternative. I downloaded a couple of compilers, read some tutorials, got the old "hello world" program to work. But I could see that implementing a GUI for Windows was over my head, as well as trying to combine C/C++ with AutoLISP<br /><br />The native programming language for AutoCAD is AutoLISP, which is LISP adapted for CAD by AutoDesk. There appears to be no way to define a variable as high precision. Calculations appear to get, uh, unstable at the 5th or 6th digit. I believe this is due to AutoCAD's implementation, as opposed to LISP itself.<br /><br />The nature of the problem is that little tiny changes to SLR result in largish changes in TOF. What happens is that the increment chosen to vary SLR ends up being of the same order as the calc precision, and the iteration begins alternating between two values.<br /><br />The only solution I can envision (using LISP alone) is to actually keep track of the results (in a stack?) and detect when and if this alternating occurs and use that to exit the loop. But this strikes me as a kluge on a kluge: will it even work? Will it just lead to, or reveal, another problem - that's the history of this thing for me. It also seems like I will end up with an imprecise answer for which I will always be making apologies and disclaimers.<br /><br />I'm quite good at LISP, so that's why it's written in LISP (If your only tool is a hammer all problems look like a nail). But the intention was always that what I've done was to be a prototype for a <i>real</i> program.<br /><br />Given the time, I could re-write the whole thing in C/C++, but it's a big project and my inexperience would no doubt show up in clunky code. Plus it would have no graphical output, so folks would not be able to see what's going on. AutoCAD is great for that.<br /><br />I wonder how hard it would be to write just the iteration routine in C/C++ and ca <div class="Discussion_UserSignature"> </div>

 

[arobie]

<i>"Before moving on to the actual question, in the next post, I would first like to ask if anyone is interested in the results."</i><br /><br />I just wanted to pipe up to say that I am interested in the results. I haven't the slightest idea how to help you, (and I'm sorry for that, wish I could help you) but I wish you luck in fixing it and hope you post the results you get from your program.<br /><br /><i>"sometimes I think I’m the only one who cares."</i><br /><br />You are not.

 

[igorsboss]

In this situation, many computer scientists would add a parameter for the maximum number of loop iterations to attempt before giving up. If your loop goes that many times without a solution, then just give up, and report "Error: Solution failed to converge in 50000 iterations."<br /><br />That is guaranteed to turn an infinite loop into a finite loop, but it is not guaranteed to be satisfying. In this case, you might consider reporting the best solution found so far and leave it at that.<br /><br />Some cases to consider next:<br />* Perhaps more iterations might have worked. This is usually not the case.<br />* Perhaps the SLR increment/decrement needs to be finer, for better resolution. (More on this below)<br />* Perhaps the solution is sensititve to the initial value. Unlikely after 50K iterations.<br />* Perhaps the rather complicated function SLR=f(TOF) is not monotonic near the solution (possibly due to discrete math effects). In this case, the solution might be in the opposite direction than where you thought it was. In this case, a shotgun approach might help.<br />* Perhaps there no solution exists which is expressible using this discrete computer system. In this case, the best you can hope to do is to give up quickly, and report the best solution found so far.<br /><br />I suppose you have already proven to yourself on paper (using the mean value theorem from Calculus) that a solution must exist. And you would be right, since space travel trajectory is a continuous function. The problem could very well be with the discrete math of the computer.<br /><br />Stay tuned for my next post...<br />

 

[spacester]

Yeah, I'm pretty sure the problem is with the, uh, discrete math. If I understand what that means exactly.<br /><br />The thing is, my routine is quite clunky. I start with an increment, when I get agreement to two significant digits, I divide that increment by ten and loop till the next digit agrees, and so on. I need more digits of agreement than the software delivers. But only sometimes. Taken to the limit of precision possible would be OK, if it worked every time. If I start the increment at a smaller value, it takes forever and a day. I just <i>know</i> the way I'm doing it is amateurish.<br /><br />Let me know if you want to see the particular function . . . <br /> <div class="Discussion_UserSignature"> </div>

 

[spacester]

Thanks Arobie. Check your PM in a bit. <div class="Discussion_UserSignature"> </div>

 

[igorsboss]

Here's what I would do, if I got really really pissed off and I really wanted it to work. I'll call it an "iterated zooming shotgun" approach.<br /><br />In this, S is the SLR value to try, and T[7] is an array of 7 TOF values. I assume that a function g exists such that TOF=g(SLR). The variable d (delta) is the SLR increment/decrement value.<br /><br />The variable epsilon defines how close a solution needs to be in order to be considered close enough to work. If epsilon is zero, this should converge to the more precise answer possible for your system.<br /><br />I'd expect this to usually converge with N=100 iterations. If it doesn't converge with N=10000, it probably isn't ever going to converge.<br /><br />Overview:<br />1) Add an iteration counter. Loop terminates if too many iterations.<br /><br />2) Vary the increment resolution. Better guesses are rewarded with slightly finer increment resolution. Poor guesses are punished with slightly larger increment resolution. The loop terminates when the increments get so small that they are equivalent to adding or subtracting zero.<br /><br />3) On each iteration, evaluate 7 different values of S, choose the best. This is an attempt to deal with the possibility that the function g() is not monotonic at fine resolutions.<br /><br />4) If the initial guess for SLR is too wildly far off, or if the initial value for d is too wildly large, this might never converge.<br /><br />{<br />s = a reasonable guess for SLR;<br />d = a reasonable guess for the SLR delta value;<br /><br />i=0;<br />while (i++ < N) {<br /><br />T[0] = g(s-3*d);<br />T[1] = g(s-2*d);<br />T[2] = g(s-d);<br />T[3] = g(s);<br />T[4] = g(s+d);<br />T[5] = g(s+2*d);<br />T[6] = g(s+3*d);<br /><br />Let j = 0,1,2,3,4,5,or 6, such that T[j] is closer to the desired TOF value than any other value of the T array.<br /><br />switch (j) {<br />case 0: s=s-3*d; d=d*1.05; break;<br />case 1: s=s-2*d; d=d*0.95; break;<br />case 2: s=s-d; d=d*0.85; break;<br />case 3: s=s; d=d*0.67; break;

 

[spacester]

Wow.<br /><br /><img src="/images/icons/cool.gif" /><br /><br />Thanks a bunch.<br /><br />It'll take some time for this poor engineer to assimilate . . . <div class="Discussion_UserSignature"> </div>

 

[spacester]

OK, I think I see how that works.<br /><br />It's friggin brilliant! I NEVER would have come up with that by myself. Zooming shotgun, lol.<br /><br />Did you invent it yourself?<br /><br />It's gonna take a while before I find time to implement and test it, but I'll let you know when the time comes.<br /><br />Thanks again! <div class="Discussion_UserSignature"> </div>

 

[Maddad]

spacester<br />"<font color="yellow">If I start the increment at a smaller value, it takes forever and a day.</font><br /><br />Could you use a calculated increment based on the precision that you had achieved so far? That way you could use a large increment in the beginning which would crunch numbers fast, and then as you got close to the limit of precision the increment would go down. Most of the math would transpire with a large increment, so you'd only give up a little speed.<br /><br />Oh, also, work as much as you absolutely can with integers, not floating point numbers. I'm totally serious. You will cut your processing time in half at least. Most programs default to floating point numbers, so you need to specify integers at the beginning of your routine. If you're working with a number with two digits past the decimal point, just multiply them by 100 and use integers. Only convert them to floating point numbers to display the answer and you'll run a whole lot faster.

 

[igorsboss]

<font color="yellow">It's friggin brilliant! I NEVER would have come up with that by myself. Zooming shotgun, lol. </font><br /><br />Thanks. I like the name, too.<br /><br />I also like the "if ((s+d)==s)" expression, which reads as "if d is effectively zero, relative to s". That really gets to the heart of floating point math.<br /><br /><font color="yellow">Did you invent it yourself?</font><br /><br />Yup, just tonight. Thanks for the inspiration.<br /><br />Seems to me that it's a pretty neat general solution, especially if g() is well-behaved. It evaluates the function g() a bit more that it needs to, but it should pay off in the end. I'll have to stick that one in my hip pocket for later.<br /><br />BTW, the epsilon conditional is optional. If you leave it out, this will give you the best solution obtainable for the numerical representation you are working with.<br /><br />Please let me know if and how it works.<br /><br />It can be fooled if g() has lots of local minima or maxima. That's where the quality of the initial guess is important.

 

[igorsboss]

<font color="yellow">Oh, also, work as much as you absolutely can with integers, not floating point numbers. I'm totally serious. You will cut your processing time in half at least.</font><br /><br />I agree, integers a way faster than floating point. However, don't sacrifice correctness for speed when solving math problems. Real speed comes from the algorithm, not the representation.<br /><br />In the zooming shotgun, <br />d=d*1.05 represents speed,<br />d=d*0.95 represents caution,<br />d=d*0.85 represents optimism, and <br />d=d*0.67 represents accuracy.

 

[CalliArcale]

I'm glad spacester's finally getting some really useful help with this. <img src="/images/icons/wink.gif" /> I took a crack at helping him over a year ago. (No wait, it was longer than that. Ada hadn't been born yet. WOW!) But math has never been my strong suit, nor GUIs. (I'm a text junkie, which is probably why this board is so addictive to me. <img src="/images/icons/tongue.gif" /> ) Plus I never had the time. So thanks, igorsboss!<br /><br />I like the zooming shotgun too. <img src="/images/icons/wink.gif" /> <div class="Discussion_UserSignature"> <p> </p><p><font color="#666699"><em>"People assume that time is a strict progression of cause to effect, but actually from a non-linear, non-subjective viewpoint it's more like a big ball of wibbly wobbly . . . timey wimey . . . stuff."</em>  -- The Tenth Doctor, "Blink"</font></p> </div>

 

[igorsboss]

Well, Calli, I suppose I just like helping complete strangers like spaceter.

 

[vogon13]

Interesting project. I have neither the math or computer skills to offer any help there. Have wondered since the 'lost' Amphitrite Galileo flyby about a probe trajectory that starts at earth, crosses the asteroid belt and has a couple of nice asteroid flybys, proceeds outward to encounter a leading Jupiter trojan asteroid, starts to arc around quite aways out bound of Jupiter to allow enough time for trailing Jupiter trojan asteroid to come by to line up with sun ward fall of probe for another flyby . Crossing asteroid belt again and doing 1 or 2 more asteroid flybys and then coming back to earth for a gravity redirect to do something like that again. Realize this mission takes long time, but once its in flight you get to look forward to all kinds of good asteroid data. Maybe outbound of Jupiter could encounter comet nucleus while its quiet. Curious about that now that we have seen them in active state. Never had a clue how to set up trajectories and ephemeri to see if this path is even remotely doable.<br /><br /><br /><br />Where a Ford's affordable for you<br />McFadden Ford ad jingle <div class="Discussion_UserSignature"> <p><font color="#ff0000"><strong>TPTB went to Dallas and all I got was Plucked !!</strong></font></p><p><font color="#339966"><strong>So many people, so few recipes !!</strong></font></p><p><font color="#0000ff"><strong>Let's clean up this stinkhole !!</strong></font> </p> </div>

 

[spacester]

Well now, it looks like I've got the whole thing running reliably now. There were actually 3 different causes for it to get into an infinite loop!<br /><br />I found a constant buried deep in a routine that wasn't entered to enough decimal places, and that made the whole tof = f(slr) thing go away! I was getting ready to implement the zooming shotgun but I happened across that error, and *wolla* the problem is solved!<br /><br />I found a value that wasn't getting re-calculated as required and that fix made another class of stalling go away. This one had to do with calculating trips near the Hohmann time.<br /><br />Thirdly I found a simple accuracy parameter that needed to get re-adjusted after earlier tweaking. <br /><br />I thought I had already fine-tooth combed the code, but one more survey did the trick. And it only took an hour and a half to find and fix three problems, I am one happy camper.<br /><br />I have good reason to believe the thing is now bulletproof, which is more than I was hoping for just a short time ago. So I tweaked the routine that runs multiple cases in nested loops, and massaged the data format for the output files.<br /><br />All of which means I'm soon going to have a database - a compilation of flight paths to and from Mars for the years 2003 thru 2045. The data will range from trip times near Hohmann all the way down to the fastest possible "one-tangent" trips, in increments of 2 days.<br /><br />If it runs all night, I'll know I can get the data, it'll just be a matter of processing it to make a database.<br /> <div class="Discussion_UserSignature"> </div>

 

[spacester]

All Right!<br /><br />It's still running, good looking data sets so far . . . <br /><br />This means I can create a master spreadsheet workbook and offer that as freeware. Rather than run code, you would just look up the answer. Or do your own processing as you see fit. Sounds cool, yes?<br /> <div class="Discussion_UserSignature"> </div>

 

[arobie]

Excellent Spacester!<br /><br />Congratulations on the fix. <img src="/images/icons/smile.gif" /><br /><br /><font color="yellow">This means I can create a master spreadsheet workbook and offer that as freeware.</font><br /><br />I would like one!

 

[igorsboss]

<font color="yellow">Excellent Spacester! </font><br /><br />I'll second that! I'd like a copy of that workbook, too.