کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874105 | 1441022 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reaching a target in the plane with no information
ترجمه فارسی عنوان
دستیابی به هدف در صفحه بدون اطلاعات
همین الان دانلود کنید
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اکتشاف، الگوریتم، عامل متحرک، سرعت، هزینه، صفحه
فهرست مطالب مقاله
چکیده
کلمات کلیدی
1. مقدمه
۲. سناریوی ایستا
۳. سناریوی پویا
۴. نتیجهگیری
کلمات کلیدی
1. مقدمه
۲. سناریوی ایستا
۳. سناریوی پویا
۴. نتیجهگیری
ترجمه چکیده
عامل متحرک باید به هدفی در صفحهی اقلیدسی برسد. هم عامل و هم هدف هر دو به صورت نقاط مدلسازی میشوند. در ابتدا عامل در فاصلهی حداکثر D>0 از هدف قرار دارد. عامل برای رسیدن به هدف به فاصلهی ادراک حداکثر r>0 از هدف میرسد. عامل دارای مقیاس طول و یک قطبنما است. در اینجا دو سناریو را درنظر میگیریم: هدف در سناریوی ایستا ساکن است و در سناریوی پویا به صورت دلخواه با هر سرعت محدود به v (احتمالا متغیر) حرکت میکند. عامل هیچ اطلاعاتی دربارهی پارامترهای مسئله به ویژه D، r یا v ندارد. هدف مسئله رسیدن به نقطهی هدف با کمترین هزینهی ممکن است که بر اساس طول کل مسیر عامل اندازهگیری میشود.
نتیجهی اصلی ما رسیدن به هزینهی مینیم (تا ثابتهای ضربی) برای رسیدن به هدف در دو سناریو و ارائهی الگوریتمی بهینه برای عامل است. هزینهی مینیمم برای سناریوی ایستا برابر با (فرمول) و برای سناریوی پویا برابر با (فرمول) است. در سناریوی دوم سرعت عامل در الگوریتم به صورت نمایی همراه با زمان رشد میکند و ثابت میکنیم برای هر عاملی که سرعتش تنها به صورت چندجملهای به مرور زمان رشد میکند، دستیابی به این هزینه غیرممکن است.
© 2018 Elsevier B.V. تمام حقوق محفوظ است.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Our main result is establishing the minimum cost (up to multiplicative constants) of reaching the target under both scenarios, and providing the optimal algorithm for the agent. For the static scenario the minimum cost is Î((logâ¡D+logâ¡1r)D2/r), and for the dynamic scenario it is Î((logâ¡M+logâ¡1r)M2/r), where M=maxâ¡(D,v). Under the latter scenario, the speed of the agent in our algorithm grows exponentially with time, and we prove that for an agent whose speed grows only polynomially with time, this cost is impossible to achieve.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 140, December 2018, Pages 13-17
Journal: Information Processing Letters - Volume 140, December 2018, Pages 13-17
نویسندگان
Andrzej Pelc,