سینا پرس:تصور کنید که به تلفن همراهتان بگویید، میخواهید از خانهتان به هتلی در شهر دیگر بروید و برای استراحت در بین راه توقف کنید و اینکه نمیخواهید مدت سفرتان بیشتر از چهار ساعت به طول بیانجامد. سپس متصور شوید که تلفن همراه شما در پاسخ بگوید که شانس شما برای برآوردن این شرط تنها 66 درصد است و اگر زمان استراحت را کاهش دهید یا حذف کنید در آنصورت با احتمال 99 درصد موفق به برآوردن شرط مسافرت چهار ساعته خواهید شد.
یک چنین اپلیکیشنی هدف اصلی گروه برایان ویلیامز در آزمایشگاه هوش مصنوعی و علوم کامپیوتر دانشگاه امآیتی است. اگرچه چارچوب اساسی این هدف بر اساس نرم افزاری است که ناسا و موسسه اقیانوسشناسی وودز هول برای برنامهریزی در ماموریتهایشان استفاده کردهاند.
در نشست سالانه انجمن توسعه هوش مصنوعی (AAAI) که در همین ماه برگزار خواهد شد، پژوهشگران گروه تحقیقاتی ویلیامز الگوریتمی را معرفی خواهند کرد که نشان دهنده پیشرفت قابل توجهی نسبت به آنچه ویلیامز به عنوان «siri بهتر» توصیف میکند خواهد بود.
سیری اپل (Apple Siri) در واقع اپلیکیشنی است که در سیستم عامل آیاواس مورد استفاده قرار میگیرد و یک دستیار شخصی هوشمند و راهنمای دانا است. این اپلیکیشن هوشمند از صدای انسان برای پاسخ دادن به سوالات، توصیه کردن به کاربر و انجام بعضی از سرویسها و فرامین صوتی کاربر استفاده میکند. به این معنی که با این اپلیکیشن فقط از طریق صدا میتوان ارتباط داشت. البته این سرویس برای زبانهای انگلیسی، آلمانی و فرانسوی وجود دارد و یک اپلیکیشن تحت وب است. این اپلیکیشن برای هر کاری که نیاز به برنامه ریزی دارد مثلا، برنامهریزی پرواز و یا مسیرهای اتوبوس مفید است.
پنگ یو و چنگ فنگ که هردو از فارغالتحصیلان بخش هوانوردی و فضانوردی دانشگاه امآیتی هستند به همراه ویلیامز، نرمافزاری ایجاد کردند که به برنامهریز اجازه میدهد قیدها و آستانه قابلیت اطمینان را تعیین کند. برای مثال برنامهریز توسط این نرمافزار میتواند مشخص کند که اتوبوسهای یک مسیر ویژه باید با فواصل زمانی 10 دقیقه به مقصد خود برسند و یا اینکه در 90 درصد مواقع باید به موقع در مبدا حاضر شوند. سپس، سیستم بر اساس مدلهای احتمالاتی، (که دادههای احتمالاتی را نشان میدهند برای مثال زمان سفر در طول این مسافت از جاده بین دو تا 10 دقیقه به طول میانجامد) تعیین میکند که آیا راه حلی وجود دارد یا خیر.
با این حال، اگر راه حلی وجود نداشته باشد، نرم افزار متوقف نمیشود. بلکه، راههایی را نشان میدهد که برنامهریز بتواند قیدهای مسئله را کمتر کند؛ «آیا اتوبوسها میتوانند با فواصل 12 دقیقهای به مقصد برسند؟.» اگر برنامهریز اصلاحیه پیشنهادی را رد کند، نرم افزار جایگزینهای دیگری ارائه می دهد؛ «می توانید یک اتوبوس دیگر به مسیر اضافه کنید؟.»
قابلیت تحمل اندکی خطا
یکی از مزیتهای نرمافزار که آن را از سیستمهای برنامهریز قبلی متمایز میکند سنجیدن خطرهای احتمالی است. فنگ میگوید: «همواره کار کردن مستقیم با احتمالات دشوار است، زیرا پیچیدگی را به محاسبات وارد میکنند. به همین دلیل ایده تخصیص خطرهای احتمالی به ذهنمان رسید.»
برای مثال مدت زمان لازم برای گذراندن هر مایل از یک مسیر اتوبوس را می توان توسط توزیع احتمال نشان داد که تابع توزیع احتمال یک نمودار منحنی زنگوله مانندی است که زمان را نسبت به احتمال نمایش میدهد. با دنبال کردن هر یک از احتمالات و ترکیب کردن آنها با هر مایل از مسیر محاسبات پیچیدهای حاصل میشوند. اما اگر سیستم بداند که برنامه ریز میتواند تاثیر مقدار مشخصی از خطا را تحمل کند، آن خطا را به نتایج پایین ترین احتمال در تابع توزیع، تخصیص میدهد. به این ترتیب توزیع آنها به صورت محاسبات ریاضی بسیار آسان میشود.
در نشست سالانه انجمن توسعه هوش مصنوعی، ویلیامز و شاگردش به نام اندرو ونگ، مقالهای ارائه خواهند کرد که چگونگی ارزیابی کردن موثر چنین تخصیصهایی را برای پیدا کردن راهحل فوری مسائل برنامهریزی حلشدنی توضیح میدهد. اما مقاله دیگری توسط یو و فنگ در همان جلسه کنفرانس ارائه خواهد شد که بر شناسایی قیدهایی که از حل شدن مسائل جلوگیری میکنند تمرکز دارد.
همیشه راهی وجود دارد
هر دو روش ریشه در نظریه گراف دارند. در این زمینه، یک گراف نمایش دادهای است که از گرهها، (معمولا به صورت یک دایره به تصویر کشیده میشوند) و لبهها، (معمولا به صورت خط تیره نشان داده میشوند و گرهها را به هم متصل میکنند) تشکیل میشود. هر نوع مسئله برنامهریزی میتواند به صورت یک گراف نمایش داده شود. گرهها نشاندهنده حوادث و لبهها نشاندهنده دنبالهای است که در آن حوادث میبایست رخ دهند. همچنین هر لبه یک وزن وابسته دارد که هزینه عبور از یک حادثه به حادثه بعد را نشان میدهد، برای مثال زمانی که طول میکشد یک اتوبوس مسیر بین دو نقطه توقف را طی کند.
الگوریتم یو، ویلیامز و فنگ ابتدا هر مسئله را به صورت یک گراف نمایش میدهد، سپس شروع به اضافه کردن لبهها میکند که نشاندهنده قیدهای اعمال شده توسط برنامهریز است. اگر مشکل قابل حل باشد، وزن هر لبه به نمایندگی از قیدها در همه جا بیشتر از وزن نشاندهنده هزینههای انتقال بین حوادث خواهد بود. با این حال الگوریتمهای موجود، به سرعت در حلقههای بسته گراف که در آنها وزن نامتعادل است گیر میکنند. اما سیستم طراحی شده توسط پژوهشگران امآیتی در هنگام بروز چنین مشکلی راهی با کمترین هزینه ایجاد توازن حلقه را محاسبه میکند و آن را به عنوان تعدیل قیدهای اولیه مسئله به برنامهریز ارائه میکند.
No tags for this post.