গ্রিড এনভায়রনমেন্টে হিউরিস্টিক সার্চ অ্যালগরিদমের পারফরম্যান্স মেট্রিক্স

3 পরীক্ষামূলক পরিবেশ এবং কর্মক্ষমতা পরিমাপ

হিউরিস্টিক অনুসন্ধান অ্যালগরিদমগুলি রোবোটিক পাথফাইন্ডিংয়ের মতো ক্ষেত্রে একটি গুরুত্বপূর্ণ ভূমিকা পালন করে, কারণ তারা একটি প্রারম্ভিক অবস্থান এবং একটি লক্ষ্যের অবস্থান দেওয়া সর্বোত্তম পথ নির্ধারণ করে। গ্রিড-ভিত্তিক পরিবেশগুলি সাধারণত বাস্তব-বিশ্বের পরিবেশ পরিস্থিতি উপস্থাপনের জন্য ব্যবহৃত হয়, যেখানে এই অ্যালগরিদমগুলি প্রয়োগ করা যেতে পারে, যেমন স্বায়ত্তশাসিত নেভিগেশন এবং রোবোটিক্স [6]। এই গবেষণায়, আমরা বিভিন্ন গ্রিড পরিবেশে D*, D* Lite, LPA*, LRTA*, RTAA*, এবং ARA* নামক সুপরিচিত হিউরিস্টিক সার্চ অ্যালগরিদমগুলি ব্যাপকভাবে বিশ্লেষণ করি। আমরা অ্যালগরিদমগুলির অনুসন্ধানের জন্য গাইড করতে ইউক্লিডীয় দূরত্ব হিউরিস্টিক ব্যবহার করি এবং অ্যালগরিদমগুলির কার্যকারিতার উপর কিছু গ্রিড বৈশিষ্ট্য যেমন বাধার ঘনত্ব এবং গ্রিডের আকারের প্রভাব মূল্যায়ন করি।

আমাদের গবেষণায়, আমরা তাদের সরলতার কারণে গ্রিড-ভিত্তিক পরিবেশ ব্যবহার করি, এবং গবেষণা সম্প্রদায়ের পথ-পরিকল্পনা কার্যগুলিতে সাধারণত ব্যবহার করা ছাড়াও। গ্রিডগুলি সাদা কোষ দ্বারা গঠিত, যা অতিক্রমযোগ্য অবস্থার প্রতিনিধিত্ব করে, যেখানে কালোগুলি অ-ট্র্যাভার্সেবল বাধাগুলির প্রতিনিধিত্ব করে। আমাদের সিমুলেশনের এজেন্ট আটটি দিকে যেতে পারে, যার মূল্য অনুভূমিক এবং উল্লম্ব চালনার জন্য 1 এর সমান এবং তির্যক নড়াচড়ার জন্য √ 2। আমরা দুই ধরনের গ্রিড পরিবেশ ব্যবহার করেছি: এলোমেলোভাবে তৈরি গ্রিড পরিবেশ এবং ব্যক্তিগতকৃত গ্রিড পরিবেশ।

এলোমেলোভাবে উৎপন্ন গ্রিড-ভিত্তিক পরিবেশ: গ্রিড তিনটি পরামিতি দ্বারা চিহ্নিত করা হয়:

গ্রিডের আকার (NxN), বাধার ঘনত্ব এবং শুরু এবং লক্ষ্যের মধ্যে দূরত্ব। সার্চ অ্যালগরিদমগুলির কার্যক্ষমতার উপর প্রতিটি প্যারামিটারের প্রভাব তদন্ত করতে, আমরা অন্যান্য পরামিতিগুলিকে স্থির রেখে প্রতিটি পরামিতি স্বাধীনভাবে পরিবর্তিত করেছি। বিভিন্নতার মধ্যে গ্রিডের আকারের ভিন্নতা, লক্ষ্য দূরত্বের শুরুতে পরিবর্তিত হওয়া এবং বাধার ঘনত্বের ভিন্নতা অন্তর্ভুক্ত ছিল। একটি ভিন্নতার প্রতিটি গ্রিডের জন্য, আমরা একই গ্রিড প্যারামিটারের দশটি এলোমেলো দৃষ্টান্ত তৈরি করেছি (যেমন, বাধা ঘনত্বের 0.25 সহ একটি গ্রিড, আকার 300x300, এবং 140 লক্ষ্য দূরত্বের শুরুতে, দশটি দৃষ্টান্ত রয়েছে, যা এলোমেলোভাবে তৈরি হয়েছিল)।

ব্যক্তিগতকৃত গ্রিড পরিবেশ: আরো নির্দিষ্ট পরিস্থিতিতে অনুকরণের জন্য ডিজাইন করা হয়েছে। এই গ্রিডগুলির নির্দিষ্ট আকার (71x31 ইউনিট) এবং শুরু এবং লক্ষ্য উভয় অবস্থার জন্য একটি নির্দিষ্ট অবস্থান রয়েছে এবং তাদের বাধা কনফিগারেশনের উপর ভিত্তি করে দুটি ভাগে বিভক্ত করা হয়েছিল:

• অনুভূমিক প্রাচীর কনফিগারেশন: এই পরীক্ষাগুলির জন্য, আমরা গ্রিড দৈর্ঘ্যের প্রতি 10 ইউনিট অর্ধ গ্রিড প্রস্থের অনুভূমিক দেয়াল যুক্ত করি। আমরা দেওয়ালগুলিকে দুটি অভিযোজনে যুক্ত করেছি: একবার বাম থেকে ডানে, এবং একবার ডান থেকে বামে নতুন তৈরি করা গ্রিডে৷

• অনুভূমিক প্রাচীর দৈর্ঘ্য কনফিগারেশন: এখানে, আমরা সমস্ত সম্ভাব্য দেয়াল যোগ করি যা ভিতরে স্থাপন করা যেতে পারে

গ্রিডের দৈর্ঘ্য, এবং প্রতিবার যখন আমরা একটি নতুন গ্রিড তৈরি করি তখন আমরা সমস্ত দেয়ালের দৈর্ঘ্য 2 ইউনিট বৃদ্ধি করি।

আমরা একটি পুঙ্খানুপুঙ্খ বিশ্লেষণ প্রদানের জন্য এই দুটি স্বতন্ত্র পরিবেশ গ্রহণ করেছি, দুটি ভিন্ন প্রতিবন্ধক পরিস্থিতির উপস্থিতিতে অনুসন্ধান অ্যালগরিদমের কর্মক্ষমতা সম্পর্কে সূক্ষ্ম অন্তর্দৃষ্টি প্রকাশ করতে চাই। প্রথমটিতে, বাধাগুলি গ্রিডের মধ্যে এলোমেলোভাবে ছড়িয়ে ছিটিয়ে রয়েছে, যেখানে দ্বিতীয়টিতে, প্রাচীরের মতো কাঠামোগুলি সংযুক্ত বাধাগুলির একটি ভর হিসাবে উপস্থিত হয়।

পরীক্ষায় ব্যবহৃত বিভিন্ন অনুসন্ধান অ্যালগরিদমের কার্যকারিতা মূল্যায়ন করতে, আমরা নিম্নলিখিত মেট্রিকগুলি নির্বাচন করেছি:

• পাথ খরচ: মেট্রিক পথের দৈর্ঘ্য পরিমাপ করে বা শুরু থেকে লক্ষ্য রাজ্য পর্যন্ত সম্পাদিত কর্মের সংখ্যা। এটি সমাধানের গুণমান নির্দেশ করে।

• মেমরি খরচ: এটি একটি সমাধান খুঁজে পেতে অ্যালগরিদমের জন্য প্রয়োজনীয় পরিমাণ মেমরি পরিমাপ করে। এটি অ্যালগরিদমের মাপযোগ্যতা পরীক্ষা করা প্রাসঙ্গিক, এবং এটি (KB) এ পরিমাপ করা হয়।

• সমাধানের সময়: মিলিসেকেন্ডে (মিসে) পরিমাপ করা একটি অ্যালগরিদম (ms) এ সমাধান খুঁজে পেতে মোট সময়কে উপস্থাপন করে।

আমরা 3.30GHz 27 Intel i9 কোরে আমাদের পরীক্ষা চালিয়েছি, 250Gb RAM দিয়ে সজ্জিত এবং উবুন্টু লিনাক্স 22.04 চালাচ্ছি। নিম্নলিখিত সেটিংস ব্যবহার করে: সমস্ত অ্যালগরিদম হিউরিস্টিক ফাংশন হিসাবে ইউক্লিডীয় দূরত্ব ব্যবহার করছিল। LRTA* এবং RTAA*-এর জন্য, আমরা প্রতিটি পুনরাবৃত্তির জন্য ব্যয়িত নোডের সংখ্যা 250 সেট করি। ARA* অ্যালগরিদম হিউরিস্টিকের জন্য 2.5 ওজনের সাথে চালানো হয়েছিল। এলোমেলোতার জন্য এবং ফলাফলের নির্ভরযোগ্যতা নিশ্চিত করতে আমরা প্রতিটি গ্রিডে 100 বার প্রতিটি অ্যালগরিদম চালিয়েছি।