Simulation of database search algorithms towards star-identification speed enhancement

Document Type : Research Paper

Authors

1 Shahid Beheshti University, faculty of new technologies and aerospace engineering

2 Qom University, faculty of engineering

Abstract

The main challenge of the star sensor as a real-time sensor is the execution time of attitude determination. Attitude determination using the star sensor includes five main steps: star catalog and identification algorithm selection, database construction, image processing, star identification and finally, attitude determination. Star identification consists of the implementation of the selected identification algorithm on the field of view stars and database searching. in the process of attitude determination using the star sensor, database searching is the most time-consuming part. This paper deals with three methods for database searching and surveys the search time for each of the presented algorithms also the consideration of using them as the database search methods for the star sensor. The methods are the ternary search technique, Fibonacci search technique, and interpolation search technique. The presented algorithms have not been used so far in the star sensor database searching. To survey the influence of the database dimensions on the identification time, each of the presented methods was studied using seven databases with different dimensions. The results show the superiority of the interpolation search method.

Keywords

Main Subjects

References

[1] Bolandi, H., fanisaberi, F., Eslami Mehrjerdi, A. Design of an Attitude Controller for Large-Angle Maneuvers of a Satellite considering of Reaction Wheels Constraints with High Fidelity Model. Aerospace Knowledge and Technology Journal, 2012; 1(1): 20-30. (in Persian)
[2] Toloei AR, Arani MS, Abaszadeh M. A new composite algorithm for identifying the stars in the star tracker. International Journal of Computer Applications. 2014 Jan 1;102(2).
[3] Spratling BB, Mortari D. A survey on star identification algorithms. Algorithms. 2009 Mar;2(1):93-107.
[4] Roshanian J., Yazdani SH, Ebrahimi M. Consideration on Actualizing the Non-Dimensional Star Pattern Recognition Algorithm for a Typical Laboratory Star Tracker. Journal of Space Science and Technology, 2012; 5(2). (in Persian)
[5] Nikkhah, A., somayehee, F., Roshanian, J. Simulation of Night Sky Images with an Ideal Pinhole Model for a Star Sensor. Journal of Space Science and Technology, 2018; 11(3): 21-32. (in Persian)
[6] Markley FL, Mortari D. Quaternion attitude estimation using vector observations. The Journal of the Astronautical Sciences. 2000 Jun;48(2):359-80.
[7] Mortari D, Neta B. K-vector range searching techniques. Naval Postgraduate School, Monterey, California. 2014.
[8] Toloei A, Zahednamazi M, Ghasemi R, implementation of the database searching methods to survey the speed of attitude determination in the star sensor, 19th international conference of Iranian aerospace society,2021. (in Persian)
[9] Roshanian J., Hasani S.M, Yazdani SH, Ebrahimi M. Star Catalog Criteria Selection and Mission Catalog Update for a Typical Star Tracker. Journal of Space Science and Technology, 2013; 5(4). (in Persian)
[10] Sedaghat H., Toloei A., Ghanbarpour H.,    Automatic Star Identification Using Triangle Base and Increase Search Speed. Journal of Space Science and Technology, 2012; 4(4). (in Persian)
[11] Toloei A, Zahednamazi M, Ghasemi R, Mohammadi F. A comparative analysis of star identification algorithms. Astrophysics and Space Science. 2020 Apr;365(4):1-9.
[12] Rijlaarsdam D, Yous H, Byrne J, Oddenino D, Furano G, Moloney D. A survey of lost-in-space star identification algorithms since 2009. Sensors. 2020 Jan;20(9):2579.
[13] Mortari D, Samaan MA, Bruccoleri C, Junkins JL. The pyramid star identification technique. Navigation. 2004 Sep;51(3):171-83.
[14] Zahednamazi M, Toloei A, Ghasemi R. Different types of star identification algorithms for satellite attitude determination using star sensor. Aerospace Systems. 2021 May 18:1-7.
[15] Bajwa MS, Agarwal AP, Manchanda S. Ternary search algorithm: Improvement of binary search. In2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom) 2015 Mar 11 (pp. 1723-1725). IEEE.
[16] Ferguson DE. Fibonaccian searching. Communications of the ACM. 1960 Dec 1;3(12):648.
[17] Nishihara S, Nishino H. Binary search revisited: Another advantage of Fibonacci search. IEEE transactions on computers. 1987 Sep;100(9):1132-5.
[18] Horla D, Sadalla T. Optimal tuning of fractional-order controllers based on Fibonacci-search method. ISA transactions. 2020 Sep 1;104:287-98.
[19] Etminaniesfahani A, Ghanbarzadeh A, Marashi Z. Fibonacci indicator algorithm: A novel tool for complex optimization problems. Engineering Applications of Artificial Intelligence. 2018 Sep 1;74:1-9.
[20] Knuth DE. The art of computer programming. Vol. 3: Sorting and searching. Reading. 1973.
[21] Peterson, W. Wesley. "Addressing for random-access storage." IBM journal of Research and Development 1, no. 2 (1957): 130-146.  
[22] Gonnet GH, Rogers LD. The interpolation-sequential search algorithm. Information Processing Letters. 1977 Aug 1;6(4):136-9.
[23] Kudryavtseva I, Efremov A, Panteleev A. Optimization of helicopter motion control based on the aggregated interpolation model. InAIP Conference Proceedings 2019 Nov 22 (Vol. 2181, No. 1, p. 020008). AIP Publishing LLC.
[24] Kaporis A, Makris C, Sioutas S, Tsakalidis A, Tsichlas K, Zaroliagis C. Dynamic interpolation search revisited. International Colloquium on Automata, Languages, and Programming 2006 Jul 10 (pp. 382-394). Springer, Berlin, Heidelberg.
[25] Rahim R, Nurarif S, Ramadhan M, Aisyah S, Purba W. Comparison Searching Process of Linear, Binary and Interpolation Algorithm. InJournal of Physics: Conference Series 2017 Dec 1 (Vol. 930, No. 1, p. 012007). IOP Publishing.

Files

Share

How to cite

Statistics