একটি নির্ভুল মানচিত্র ও নিজস্ব অবস্থান পাওয়ার পর রোবটকে তার শুরু বিন্দু (q_{ ext{start}}) থেকে গন্তব্য (q_{ ext{goal}})-এ পৌঁছানোর জন্য একটি সংঘর্ষমুক্ত পথ খুঁজে বের করতে হয়। একে বলা হয় মোশন প্ল্যানিং (Motion Planning)। রোবটের উচ্চ-মাত্রিক কনফিগারেশন স্পেস ((mathcal{C})-Space)-এর ভেতর এই অ্যালগরিদমগুলো ডিসক্রিট গ্রাফ সার্চ (যেমন A*) থেকে শুরু করে অবিচ্ছিন্ন সম্ভাব্যতাভিত্তিক স্যাম্পলিং (যেমন RRT*) পর্যন্ত বিস্তৃত।
১. কনফিগারেশন স্পেস ((mathcal{C})-Space) জ্যামিতি
বাস্তব জগতে ত্রিমাত্রিক আকারের কোনো রোবটের সাথে বাধার সংঘর্ষ পরীক্ষা করা অনেক জটিল। ১৯৭৯ সালে টমাস লোজানো-পেরেজ (mathcal{C})-Space ধারণাটি প্রবর্তন করেন: রোবটের প্রতিটি জয়েন্টের কোণকে একটি করে অক্ষ ধরে একটি উচ্চ-মাত্রিক স্থান কল্পনা করা হয়, যেখানে বিশাল আকারের রোবটটি সংকুচিত হয়ে একটিমাত্র ক্ষুদ্র বিন্দুতে ((mathbf{0})) পরিণত হয়।
বাস্তব বাধাগুলোকে রোবটের আকারের সমান মিনকোভস্কি যোগফল (Minkowski Sum) দিয়ে ফুলিয়ে তৈরি করা হয় (mathcal{C}_{ ext{obs}})। ফলে পথ খোঁজার সমস্যাটি মুক্ত স্থান (mathcal{C}_{ ext{free}})-এর ভেতর দুটি বিন্দুর মধ্যে সরল পথ খোঁজার জ্যামিতিক সমস্যায় রূপান্তরিত হয়।
২. ডিসক্রিট গ্রাফ সার্চ: ডায়াকস্ট্রা বনাম A* অ্যালগরিদম
ম্যাপকে গ্রিড আকারে ভাগ করলে গ্রাফ সার্চ অ্যালগরিদম প্রয়োগ করা যায়:
- ডায়াকস্ট্রা (Dijkstra): সব দিকে সমানভাবে পথ খুঁজতে থাকে। এটি সবচেয়ে ক্ষুদ্রতম পথ নিশ্চিত করলেও গন্তব্যের উল্টো দিকেও অহেতুক পথ খুঁজে সময় নষ্ট করে।
- A* সার্চ: গন্তব্যের আনুমানিক দূরত্ব বা হিউরিস্টিক (h(n)) ব্যবহার করে গন্তব্যের অভিমুখে অনুসন্ধানকে পরিচালিত করে: (f(n) = g(n) + h(n))। যদি হিউরিস্টিক সত্য দূরত্বের চেয়ে বেশি অনুমান না করে (Admissible), তবে A* সর্বনিম্ন নোড পর্যবেক্ষণ করে নিখুঁত সংক্ষিপ্ত পথ বের করে দেয়।
৩. উচ্চ-মাত্রিক রোবট ও র্যাপিডলি-এক্সপ্লোরিং র্যান্ডম ট্রিজ (RRT)
৬ বা ৭ জয়েন্টের রোবট আর্মের ক্ষেত্রে গ্রিড পদ্ধতিতে মেমোরি ও গণনার জটিলতা সূচকীয় হারে ((mathcal{O}(k^n))) বাড়ে। ১৯৯৮ সালে স্টিভেন লাভাল উদ্ভাবন করেন RRT অ্যালগরিদম:
- স্পেস থেকে এলোমেলো একটি বিন্দু (q_{ ext{rand}}) নির্বাচন করা হয়।
- বর্তমান ট্রির সবচেয়ে কাছের নোড খুঁজে সেই দিকে এক ধাপ এগিয়ে নতুন নোড (q_{ ext{new}}) যোগ করা হয়।
- এভাবে একটি বৃক্ষের মতো শাখা-প্রশাখা ছড়িয়ে রোবট মুক্ত স্থান দ্রুত অন্বেষণ করে গন্তব্যে পৌঁছায়। কিন্তু সাধারণ RRT-এর পথ অত্যন্ত আঁকাবাঁকা ও অপচয়মূলক হয়।
৪. কারামান ও ফ্রাজোলির অ্যাসিম্পটোটিক RRT* বিপ্লব
২০১১ সালে সারতাক কারামান এবং এমিলিও ফ্রাজোলি প্রমাণ করেন যে সাধারণ RRT কখনো সর্বোত্তম পথ তৈরি করতে পারে না। তারা প্রবর্তন করেন ( ext{RRT}^*):
- লোকাল রিওয়্যারিং (Rewiring): নতুন নোড যোগ করার পর আশেপাশের নোডগুলোকে পরীক্ষা করে দেখা হয় নতুন নোডের মধ্য দিয়ে গেলে তাদের পথের দূরত্ব কমে কি না। যদি কমে, তবে আগের শাখা কেটে নতুন নোডের সাথে যুক্ত করা হয়।
- নমুনার সংখ্যা বৃদ্ধির সাথে সাথে এই পুনঃসংযোগের ফলে RRT*-এর পথ গাণিতিকভাবে নিশ্চিতভাবে বৈশ্বিক ক্ষুদ্রতম পথে (Asymptotically Optimal) রূপান্তরিত হয়।
