تطبیق نقشه مبتنی بر عدم قطعیت: الگوریتم منشور فضا-زمان و k- کوتاهترین مسیر

خلاصه

دستگاه‌های آگاه از مکان را می‌توان برای ثبت موقعیت اجسام متحرک برای تجزیه و تحلیل داده‌های مکانی-زمانی بیشتر استفاده کرد. به عنوان مثال، ما می‌توانیم مسیرهایی را که یک فرد یا گروهی از افراد دنبال می‌کنند تجزیه و تحلیل کنیم تا الگوهای پنهان در داده‌های مسیر را کشف کنیم. به طور معمول، موقعیت اجسام متحرک توسط دستگاه‌های GPS ثبت می‌شود و در اکثر مواقع، موقعیت‌های ثبت‌شده با جاده‌ای که جسم حامل دستگاه دنبال می‌کند، مطابقت ندارد، به دلیل منابع مختلف خطا. بنابراین، تطبیق موقعیت واقعی جسم متحرک با یک مکان روی نقشه دیجیتال مورد نیاز است. مشکل تطبیق موقعیت های ثبت شده توسط GPS با یک شبکه جاده ای تطبیق نقشه (MM) نامیده می شود. اگرچه الگوریتم های زیادی برای حل این مشکل ارائه شده است، تعداد کمی از آنها عدم قطعیت ناشی از عدم وجود اطلاعات در مورد موقعیت جسم متحرک را در بین مکان های ثبت شده متوالی در نظر می گیرند. در این مقاله، ما رابطه بین تطبیق نقشه و عدم قطعیت را مطالعه می‌کنیم و یک الگوریتم MM جدید پیشنهاد می‌کنیم که از منشورهای فضا-زمان در ترکیب با الگوریتم‌های وزنی k-کوتاه‌ترین مسیر استفاده می‌کند. ما الگوریتم خود را برای موارد دنیای واقعی و نمونه‌های خط سیر تولید شده توسط رایانه با ویژگی‌های مختلف اعمال کردیم. ما نتایج خود را با تعدادی از الگوریتم‌های معروفی که پیاده‌سازی کرده‌ایم مقایسه می‌کنیم و نشان می‌دهیم که از الگوریتم‌های موجود بهتر عمل می‌کند و به ما امکان می‌دهد مطابقت‌های بهتری را با کاهش عملکرد ناچیز به دست آوریم. علاوه بر این، ما یک اندازه گیری دقت جدید را پیشنهاد می کنیم که امکان مقایسه بهتر بین الگوریتم های مختلف MM را فراهم می کند.

کلید واژه ها:

تطبیق نقشه ; داده های مسیر و شی متحرک ؛ منشور فضا-زمان ؛ k – الگوریتم کوتاهترین مسیر

1. معرفی

دستگاه های GPS را می توان نه تنها به عنوان ابزار ناوبری، بلکه برای ثبت موقعیت اجسام متحرک (MOs) برای تجزیه و تحلیل داده های مکانی-زمانی بیشتر استفاده کرد [ 1]]. به عنوان مثال، ما می‌توانیم مسیرهایی را که توسط یک MO یا گروهی از MO دنبال می‌شود، تجزیه و تحلیل کنیم تا الگوهای پنهان در داده‌های مسیر را کشف کنیم. با این حال، مختصات به‌دست‌آمده با GPS، به دلیل منابع مختلف خطا، همیشه با جاده‌ای که به‌عنوان مثال یک خودرو یا یک عابر پیاده دنبال می‌شود، مطابقت ندارد. علاوه بر خطاهای اندازه‌گیری معمولی، در داده‌های دنیای واقعی، می‌توانیم ترافیک (که نقاط متوالی زیادی را با شکاف فضایی بسیار کوچک ایجاد می‌کند) یا شکاف‌های بزرگ بین دو نقطه اندازه‌گیری شده متوالی، که توسط برخی تداخل در سیگنال ماهواره ایجاد می‌شود، پیدا کنیم (به عنوان مثال، هنگام حرکت در تونل ها یا تونل های شهری). بنابراین، تطبیق موقعیت واقعی کاربر با یک مکان در نقشه دیجیتال مورد نیاز است. مشکل کلی تطبیق موقعیت های ثبت شده توسط GPS با بخش های جاده در یک شبکه جاده ای تطبیق نقشه (MM) نامیده می شود [ 2 ]].

الگوریتم‌های زیادی برای حل مسئله MM پیشنهاد شده‌اند، اگرچه هیچ یک از آنها عدم قطعیت ناشی از عدم وجود اطلاعات در مورد موقعیت MO در بین مکان‌های ثبت‌شده متوالی را در نظر نمی‌گیرند. یک مشکل رایج در پایگاه داده های شی متحرک (MOD) بازسازی یک مسیر از یک نمونه مسیر است [ 3]]. درونیابی خطی بین نقاط نمونه، که فرض می کند اجسام با حداقل سرعت ثابت حرکت می کنند، یک راه حل کلاسیک است. یک مدل واقعی تر مبتنی بر مفهوم عدم قطعیت است. برای مثال، منشورهای فضا-زمان را می‌توان برای مدل‌سازی موقعیت‌های ناشناخته، اما ممکن یک MO بین نقاط نمونه، با استفاده از اطلاعات پس‌زمینه، مانند محدودیت‌های سرعت، استفاده کرد. منشور فضا-زمان به‌عنوان پوششی عمل می‌کند که تمام مکان‌های ممکنی را که یک MO می‌تواند بین نقاط نمونه اندازه‌گیری شده متوالی، با توجه به محدودیت سرعت، بازدید کرده باشد، در بر می‌گیرد.

در این مقاله، ما رابطه بین MM و عدم قطعیت را مطالعه می کنیم. سهم اصلی ما یک الگوریتم جدید MM است که از منشورهای فضا-زمان ترکیب شده با الگوریتم های وزنی k- کوتاه ترین مسیر استفاده می کند [ 4 ]. این الگوریتم برای طیف وسیعی از انواع نمونه مسیر قابل اجرا است. به طور خلاصه، ابتدا بخش‌هایی از شبکه راه را با محاسبه، برای هر جفت نقطه نمونه متوالی، بخش‌های جاده‌ای که MO می‌توانست روی آن‌ها حرکت کند (با استفاده از جعبه‌های مرزی پیش‌بینی منشورهای فضا-زمان) انتخاب می‌کند. سپس، برای هر نقطه نمونه، الگوریتم نزدیکترین بخش جاده را محاسبه می کند و امتیازهایی را به هر بخش جاده اختصاص می دهد. در نهایت، الگوریتم، در شبکه جاده محدود (همانطور که در مرحله اول تعیین شد)، k را محاسبه می‌کند-کوتاهترین مسیرها (پیمودن کوتاهترین مسیر با بالاترین امتیاز محاسبه شده در مرحله دوم).

ما الگوریتم خود را برای موارد دنیای واقعی و همچنین برای نمونه‌های خط سیر تولید شده توسط رایانه با ویژگی‌های مختلف اعمال کردیم. مشاهدات در فواصل منظم کوچک و در فواصل بزرگتر و نامنظم انجام می‌شوند تا تمایز کلاسیک بین نرخ نمونه‌برداری پایین و نمونه‌برداری بالا در داده‌های مسیر را نشان دهند. ما همچنین نتایج خود را با تعدادی از الگوریتم‌های معروفی که پیاده‌سازی کرده‌ایم مقایسه کردیم. نتایج ما نشان می دهد که الحاق عدم قطعیت در فرآیند MM منجر به دستیابی به تطابق بهتر می شود. این نتیجه مثبت تا حد زیادی زمان های طولانی تر را جبران می کند، اما در محدوده های معقول باقی می ماند. شایان ذکر است که ما انواع مختلفی از سناریوهای تجربی را تولید کرده ایم که کاربرد روش ما را در طیف گسترده ای از موقعیت ها نشان می دهد. این موضوع با توجه به اینکه،5 ]، بیشتر کارها در این زمینه محیط آزمایش را به وضوح مشخص نمی کنند و مقایسه پیشنهادها را دشوار می کند. ما معتقدیم که با پیاده‌سازی کلاسیک‌ترین الگوریتم‌ها و مقایسه این پیاده‌سازی‌ها با پیشنهاد ما در طیف گسترده‌ای از سناریوها به قابل اعتمادتر کردن نتایج ما کمک می‌کند.

به عنوان کمک دوم، به مشکل مقایسه دقیق عملکرد الگوریتم‌های MM در برابر یکدیگر می‌پردازیم. ما ویژگی‌های احتمالی نمونه‌های مسیر و تکنیک‌ها را برای به دست آوردن مجموعه‌های داده با این ویژگی‌ها بررسی می‌کنیم. ما همچنین تعدادی از روش‌های موجود برای اندازه‌گیری دقت الگوریتم MM را بر روی این انواع مختلف مجموعه داده‌ها مورد بحث قرار می‌دهیم. ما یک اندازه گیری دقت جدید به نام دقت منحنی و طولی را پیشنهاد می کنیم که با ترکیب نقاط قوت آن روش ها، از اشکالات آنها رنج نمی برد. ما این معیار جدید را برای مقایسه الگوریتم خود با الگوریتم‌های MM موجود، همانطور که در بالا توضیح دادیم، اعمال کردیم.

سازمان

ادامه مقاله به شرح زیر تدوین شده است. در بخش 2 ، ما یک نمای کلی از الگوریتم‌های اصلی MM موجود را ارائه می‌کنیم. در بخش 3 ، پس از بررسی مفهوم منشورهای فضا-زمان، الگوریتم MM خود را ارائه می کنیم. بخش 4 روش جدید ما را برای ارزیابی الگوریتم‌های MM معرفی می‌کند که در بخش 5 از آن برای ارزیابی الگوریتم خود در برابر پیشنهادهای موجود استفاده می‌کنیم. ما در بخش 6 نتیجه می گیریم .

2. مروری بر رویکردهای موجود برای تطبیق نقشه

در بالا ذکر کردیم که، معمولاً، زمانی که موقعیت یک MO با استفاده از GPS نظارت می‌شود، بخش بزرگی از نقاط فضا-زمان ثبت‌شده خارج از شبکه جاده‌ای واقع می‌شوند که تا حدی به دلیل خطاهای اندازه‌گیری است. با این حال، مشکلات دیگری نیز در مورد داده های دنیای واقعی وجود دارد، مانند ترافیک و شکاف های بزرگ بین نقاط اندازه گیری شده فضا-زمان. این شکاف ها به دلایل مختلفی ظاهر می شوند، به عنوان مثال: (الف) سیگنال GPS معیوب. (ب) قطع ارتباط؛ یا (ج) داده های مبهم. مورد (الف) ممکن است به دلیل دریافت بد مختصات رخ دهد که احتمال وقوع آن کاملاً بعید است. در مورد (ب)، وقفه در ارتباط بین ماهواره GPS و دستگاه MO ممکن است به دلیل یک منطقه جنگلی متراکم، یک تونل یا ساختمان های مرتفع باشد. مورد (ج) ممکن است زمانی ظاهر شود که جاده ها موازی باشند، و داده های GPS به اندازه کافی دقیق نیستند تا تصمیم بگیرند که کدام جاده صحیح است. همه این نوع مشکلات مستلزم نگاشت نقاط فضا-زمان اندازه گیری شده به شبکه راه هستند. تعریف یا توصیف کلاسیک زیر از مسئله MM ناشی از وایت، برنشتاین و کورنهاوزر است: یک جسم در امتداد یک سیستم (یا مجموعه) محدود از خیابان ها حرکت می کند.

\bar{N} .

یک دستگاه آگاه از موقعیت مکانی مانند GPS تخمینی را برای مکان وسیله نقلیه در تعداد محدودی از نقاط در زمان ارائه می دهد که با نشان داده می شود.

{0, 1, \dots, t}

. مکان واقعی خودرو در زمان t با نشان داده می شود

{\bar{P}}^{t}

، و برآورد نشان داده می شود

P^{t}

. تطبیق نقشه فرآیند تعیین خیابان در است

\bar{N}

که شامل

P^{t}

; یعنی خیابانی را که وسیله نقلیه در زمان t [ 2 ] در آن قرار دارد، مشخص کند. الگوریتم های زیادی برای رفع این مشکل پیشنهاد شده است. در ادامه به بررسی برخی از آنها می پردازیم.

2.1. طبقه بندی الگوریتم های تطبیق نقشه

دو طبقه‌بندی متعامد از الگوریتم‌های MM معمولاً در ادبیات یافت می‌شوند: الگوریتم‌های آفلاین در مقابل الگوریتم‌های آنلاین و نرخ نمونه‌برداری پایین در مقابل الگوریتم‌های نرخ نمونه‌برداری بالا. الگوریتم‌های MM آنلاین برای استفاده در یک موقعیت بلادرنگ، جایی که جسم هنوز در حال حرکت است، ابداع شده‌اند. به عنوان مثال یک برنامه ریز مسیر GPS در یک ماشین رانندگی است. در الگوریتم‌های MM آفلاین، داده‌های مسیر کامل یک MO موجود است و به طور کلی الگوریتم‌های این نوع داده‌ها نتایج بهتری می‌دهند.

با توجه به طبقه‌بندی دوم بالا، سرعت نمونه‌برداری از داده‌های مسیر GPS به منبع داده‌ها بستگی دارد و از یک نقطه نمونه در ثانیه تا هر نرخی که برنامه مورد نیاز است متغیر است. معمولاً بیش از یک نقطه نمونه در هر دو دقیقه به عنوان حد پایین استفاده می شود تا نمونه برداری بالا در نظر گرفته شود. با این حال، این امکان را فراهم می کند که داده ها به اشتباه طبقه بندی شوند. ما روش جدید و زیر را پیشنهاد می‌کنیم که از تعداد نمونه‌ها در هر بخش جاده برای طبقه‌بندی داده‌ها به عنوان دارای نرخ نمونه‌برداری کم یا زیاد استفاده می‌کند: اگر حداقل یک نمونه در هر بخش جاده وجود داشته باشد که یک مسیر بین دو نقطه داده شده را تشکیل می‌دهد، فرض می‌کنیم که میزان نمونه گیری بالاست در غیر این صورت، داده ها نرخ نمونه گیری پایینی دارند. برای این طبقه بندی، ما یک منطقه اطمینان را در اطراف هر نقطه GPS محاسبه می کنیم و شبکه جاده را به بخش های جاده ای که در محدوده اطمینان قرار می گیرند محدود می کنیم. این کار با کشیدن دایره ای در اطراف نقطه نمونه، با قطری برابر با خطای احتمالی اندازه گیری انجام می شود. در عمل، این اغلب در محدوده بیست و پنج متر است.شکل 1 (سمت چپ) نمونه ای از داده های مسیر نمونه با سرعت بالا را نشان می دهد. سمت راست شکل نمونه ای از داده های مسیر نمونه برداری کم را نشان می دهد.

2.2. مروری کوتاه بر الگوریتم های تطبیق نقشه

روش دیگری برای طبقه بندی الگوریتم های MM سه نوع از آنها را تعریف می کند: (الف) الگوریتم های هندسی. (ب) الگوریتم های توپولوژیکی. و (ج) الگوریتم های احتمالی. ما همچنین رویکردهای دیگری را که در این سه دسته قرار نمی گیرند، مورد بحث قرار می دهیم. ما فقط جزئیات مربوط به الگوریتم هایی را که در تنظیمات تجربی خود استفاده می کنیم (به بخش 5 مراجعه کنید ) برای مقایسه با الگوریتم پیشنهادی خود ارائه می دهیم.

2.2.1. الگوریتم های هندسی

این الگوریتم ها از شکل بخش های جاده استفاده می کنند و نحوه اتصال بخش های جاده را نادیده می گیرند. ما می توانیم آنها را به عنوان الگوریتم های “نقطه به نقطه” و “نقطه به منحنی (با یا بدون اطلاعات توپولوژیکی)” طبقه بندی کنیم. برای جزئیات به [ 6 ] و [ 2 ] مراجعه می کنیم .

در تطبیق نقطه به نقطه، هر نقطه نمونه فضا-زمان به سادگی به نزدیکترین گره (یا رأس) در شبکه راه نگاشت می شود.

تطبیق نقطه به منحنی شبیه تطبیق نقطه به نقطه است، اما نقاط فضا-زمان به جای نزدیکترین گره در شبکه جاده، با نزدیکترین بخش جاده مطابقت داده می شوند. مشکلات متعددی با این نوع الگوریتم ها وجود دارد. اول، خطاهای نمونه گیری ممکن است در داده ها رخ دهد (به عنوان مثال، زمانی که دو نقطه فضا-زمان متوالی از نظر زمانی از هم دورتر از آنچه باید باشند). علاوه بر این، نادرست بودن داده های GPS ممکن است یک نقطه فضا-زمان ثبت شده را ایجاد کند که به جاده نزدیک تر است، که در مسیر واقعی نیست. این معمولا زمانی اتفاق می افتد که جاده های موازی نزدیک به یکدیگر یا در مجاورت گذرگاه ها وجود داشته باشد. علاوه بر این، این الگوریتم‌ها فقط به اطلاعات هندسی نگاه می‌کنند و در نظر نمی‌گیرند که نقطه قبلی با کدام بخش جاده مطابقت داشته باشد.2 ]. توپولوژی شبکه راه ها در صورت امکان برای تعیین گره های کاندید استفاده می شود. فقط بخش‌های جاده‌ای که مستقیماً از بخش فعلی قابل دسترسی هستند در نظر گرفته می‌شوند. با این حال، اگر الگوریتم در تطابق قبلی اعتماد پایینی داشته باشد، به الگوریتم تطبیق نقطه به منحنی تغییر خواهد کرد. در [ 2 ]، اطمینان زمانی حاصل می شود که خطا کمتر از 0.15 کیلومتر و دو برابر خطای متوسط باشد.

2.2.2. الگوریتم های توپولوژیکی

این الگوریتم‌ها نحوه اتصال گره‌ها در شبکه راه را در نظر می‌گیرند. به طور کلی، آنها به هر بخش جاده وزن می دهند و با توجه به این وزن ها بهترین مسیر را پیدا می کنند. برخی از آنها را مورد بحث قرار می دهیم و برای بقیه خواننده را به مراجع ارجاع می دهیم. بررسی جامع الگوریتم های MM را می توان در [ 5 ] یافت.

مدل پنهان مارکوف یک فرآیند را با در نظر گرفتن بسیاری از حالت های ممکن مدل می کند [ 7 ]. در MM اعمال می شود، یک حالت می تواند یک بخش جاده باشد، و هر انتقال بین بخش های جاده را می توان مقداری احتمال نسبت داد. اندازه گیری های حالت، نقاط نمونه اندازه گیری شده هستند. نمونه هایی از این روش را می توان در [ 8 ] و [ 9 ] یافت .

الگوریتم گرینفلد [ 10 ] فقط از اطلاعات مختصات جسم استفاده می کند و از هیچ دانشی در مورد مسیر مورد انتظار سفر، سرعت سفر و مسیر استفاده نمی کند. ابتدا یک تطابق اولیه را محاسبه می کند (با استفاده از الگوریتم نقطه به نقطه). سپس، برای تعیین اینکه یک نقطه فضا-زمان با کدام بخش جاده تطبیق داده می شود، وزنی برای چندین بخش جاده کاندید محاسبه می شود.

برکاتسولاس و همکاران [ 11 ] دو نوع الگوریتم پیشنهاد کرد: افزایشی و جهانی. اولی با در نظر گرفتن تنها بخش متصل از شبکه جاده، نمونه های موقعیت را به ترتیب مطابقت می دهد. برای بهبود الگوریتم‌هایی مانند الگوریتم گرین‌فیلد، که در بالا ذکر شد، از نگاه پیش‌روی محلی استفاده می‌شود تا به جای جستجوی ساده‌ترین لبه، کدام شاخه بهترین تطابق را پیدا کند. الگوریتم جهانی ارائه شده در [ 11] سعی می کند منحنی (یعنی تعدادی از بخش های جاده متصل) را در شبکه جاده پیدا کند که تا حد امکان به مسیر دنبال شده (یعنی منحنی تشکیل شده توسط دنباله ای از نقاط GPS) نزدیک باشد. به عنوان اندازه گیری فاصله بین دو منحنی، در این مورد از فاصله Fréchet یا فاصله Fréchet ضعیف استفاده می شود. فاصله فرشه معمولاً با تشبیه شخصی که سگ خود را با استفاده از افسار راه می‌دهد توضیح داده می‌شود. شخص روی یک منحنی راه می رود، در حالی که سگ روی یک منحنی دیگر راه می رود. هر دو ممکن است در سرعت یا توقف متفاوت باشند، اما آنها اجازه ندارند به عقب بروند. فاصله قوی فرشه، طول کوتاهترین طول بند است که پیمودن هر دو منحنی را از ابتدا تا انتها ممکن می‌سازد. فاصله ضعیف Fréchet اجازه می دهد تا در منحنی ها به عقب پیمایش کنید. مشکل الگوریتم های جهانی این است که به دلیل ماهیت آنها، آنها کل شبکه را در نظر می گیرند که مسابقات خوبی را تولید می کند، اما به قیمت زمان اجرای آهسته اجرا می شود. بنابراین، در [12 ]، یک الگوریتم برش تطبیقی پیشنهاد شده است که سعی می‌کند زمان اجرای الگوریتم جهانی را با استفاده از تخمین حرکت بدترین حالت برای هرس شبکه جاده بهبود بخشد. یک تخمین خطا، بر اساس حداکثر سرعتی که جسم می تواند با آن حرکت کند، با استفاده از بیضی خطا استفاده می شود.

سایر الگوریتم های پیشرفته بر اساس فیلترهای کالمن [ 13 ] هستند. به عنوان مثال، در [ 14 ]، یک “فیلتر کالمن گسترده” برای خطی کردن یک مسیر استفاده می شود. در لی و همکاران [ 15 ]، یک الگوریتم MM توپولوژیکی ارائه شده است که در آن داده‌های GPS، DRsensors و DEM ابتدا یکپارچه می‌شوند. بخش‌های کاندیدا به قسمت قبلی متصل می‌شوند و از نزدیکی و مسیر به عنوان وزنه‌ها برای یافتن بخش جاده درست استفاده می‌کنند.

2.2.3. الگوریتم های احتمالی

این الگوریتم ها از یک منطقه اطمینان در اطراف هر نقطه نمونه برای محاسبه یک نقطه تطبیق در شبکه جاده استفاده می کنند. این منطقه اطمینان مبتنی بر واریانس های خطای است که نقاط فضا-زمان معمولاً دارند. به عنوان نمونه ای نماینده، ما الگوریتم Ochieng، Quddus و Noland را مورد بحث قرار می دهیم [ 16 ]. مانند بسیاری از الگوریتم‌های دیگر، این الگوریتم شامل یک فرآیند نگاشت اولیه است که تطابق اولیه را پیدا می‌کند و یک فرآیند نگاشت بعدی. مانند الگوریتم منشورهای فضا-زمان که بعداً مورد بحث قرار گرفت، یک ناحیه در اطراف هر نقطه فضا-زمان محاسبه می شود. تفاوت اصلی این است که این الگوریتم از مفاهیم احتمال برای انتخاب فوری هر مسابقه جاده استفاده می کند، در حالی که الگوریتم منشور فضا-زمان وزنی را به هر بخش نسبت می دهد و سپس از k استفاده می کند.-کوتاه ترین مسیرها برای یافتن مطابقت (ما k را توضیح می دهیم-الگوریتم کوتاهترین مسیرها در زیر). بخش های جاده ای که در منطقه اطمینان قرار دارند، بخش های نامزد در نظر گرفته می شوند. اگر فقط یک بخش وجود داشته باشد، انتخاب می شود. در غیر این صورت، اتصال پیوند، اطلاعات عنوان، نزدیکی به بخش مورد نظر و اطلاعات تاریخی برای انتخاب یکی استفاده می شود. الگوریتم در نظر می‌گیرد که جسم در همان بخش جاده باقی می‌ماند تا زمانی که به یک تقاطع برسد یا یک مانور چرخشی تشخیص داده شود. هر زمان که این اتفاق بیفتد، فرآیند تطبیق اولیه دوباره فراخوانی می شود و یک بخش جاده جدید انتخاب می شود. تشخیص مانور چرخشی بر اساس سرعت جسم، زمان انجام چرخش و تغییر در زاویه حرکت است. پس از تطبیق یک نقطه فضا-زمان با یک بخش جاده، تخمینی از محل قرارگیری جسم در بخش جاده محاسبه می شود.

الگوریتم های مبتنی بر منطق فازی [ 17 ] اولین بار توسط ژائو [ 18 ] ارائه شد . روش او فقط نقاط فضا-زمان را با یک بخش شبکه جاده ای نزدیک منطبق می کند. سید و کانن این رویکرد را با استفاده از ورودی های بیشتر و تطبیق نقطه فضا-زمان با مکانی در بخش جاده بهبود می بخشند [ 19 ]. Quddus این الگوریتم را با استفاده از ورودی‌های فازی حتی بیشتر و همچنین با استفاده از اطلاعات اتصال و مسیر تاریخی شی بهبود می‌بخشد [ 20 ]. الگوریتم دوم بسیار شبیه به گرینفلد است، اما وزن با استفاده از منطق فازی محاسبه می شود.

2.3. الگوریتم‌هایی برای داده‌ها با نرخ نمونه‌گیری پایین

بسیاری از الگوریتم‌های بالا به نرخ نمونه‌گیری بالا برای تولید نتایج معنادار نیاز دارند. از آنجایی که همه داده‌ها نرخ نمونه‌گیری به اندازه کافی بالا ندارند، الگوریتم‌هایی مورد نیاز هستند که بتوانند داده‌های نرخ نمونه‌برداری پایین را مدیریت کنند. ما در مورد برخی از آنها به طور جداگانه نظر می دهیم، اگرچه می توانند در یکی از دسته بندی های ذکر شده در بالا قرار گیرند.

یکی از معرف ترین آثار در این دسته، الگوریتم تطبیق ST [ 21 ] است. این الگوریتم ابتدا نقاط کاندید را تولید می کند و سپس از طریق تحلیل مکانی (با استفاده از فاصله بین یک نقطه فضا-زمان و یک قطعه جاده) و زمانی (با استفاده از میانگین سرعت بین نقاط متوالی) به هر نقطه کاندید وزن می دهد. سپس مسیر با بیشترین وزن انتخاب می شود. احتمالات اندازه گیری نیز محاسبه می شود و به جای مدل سازی نویز با توزیع گاوسی میانگین صفر، از توزیع نرمال استفاده می شود. احتمال انتقال مانند مدل مارکوف پنهان محاسبه می شود.

لی و همکاران [ 22 ] یک الگوریتم به اصطلاح MM چند مسیری (در مقابل MM تک مسیری سنتی) پیشنهاد می کند. منطق پشت این روش مشاهده این است که در بسیاری از موارد، اجسام متحرک طبق یک الگو حرکت می کنند، بنابراین آنها تکنیک های MM را برای گروهی از مسیرها در یک نمونه اعمال می کنند و نه به صورت جداگانه. به عبارت دیگر، آنها به طور همزمان مجموعه ای از مسیرها را با یک نقشه مطابقت می دهند. نویسندگان برخی از نتایج اولیه تجربی را گزارش می‌کنند، با نمونه‌های داده‌ای که فاصله زمانی بین یک تا پنج دقیقه دارند، اما ویژگی‌های شبکه و نمونه‌ها به طور کامل مشخص نشده‌اند، که مقایسه با کار دیگر را دشوار می‌کند. نویسندگان همچنین کار مهمی را که باید انجام شود (مثلاً تعیین فاصله نقطه به منحنی مناسب) گزارش می دهند.

تانگ و همکاران [ 23 ] یک رویکرد برنامه نویسی پویا، همراه با مسیرهای فضا-زمان (به جای منشورهای فضا-زمان) برای مدیریت داده های مسیر عدم قطعیت ارائه می دهد، اگرچه ما فکر می کنیم که آزمایش ها در مورد کارایی روش، به ویژه در شرایط نرخ نمونه گیری کم، قطعی نیستند. .

چن و همکاران [ 24 ] همچنین یک الگوریتم برنامه‌نویسی پویا چند معیاره برای MM با داده‌های فرکانس پایین، با استفاده از روش کوتاه‌ترین مسیر برای یافتن بخش‌های جاده کاندید بین دو نقطه GPS متوالی پیشنهاد کرد.

از دیگر آثاری که قابل ذکر است، آثار وانگ و همکاران هستند. [ 25 ]، موریکاوا و همکاران. [ 26 ]، رحمانی و همکاران. [ 27 ]، هانتر و همکاران. [ 28 ] و Zeng و همکاران. [ 29 ]. به خاطر فضا، ما بیشتر در مورد آنها اظهار نظر نمی کنیم.

شایان ذکر است که همه آثار ذکر شده در بالا، فواصل زمانی اسمی را برای تمایز بین داده‌های نرخ نمونه‌گیری پایین و بالا در نظر می‌گیرند. در مقابل این، در بخش 2.1 ، معیار واقعی تری برای این موضوع ارائه می کنیم که توپولوژی شبکه را در نظر می گیرد.

3. الگوریتم تطبیق نقشه مبتنی بر عدم قطعیت

در بخش قبل، یک مرور کلی از الگوریتم‌های MM موجود ارائه کردیم. در این بخش، ما یک الگوریتم جدید پیشنهاد می‌کنیم که از عدم قطعیت ناشی از مکان ناشناخته یک MO بین نقاط فضا-زمان نمونه‌برداری شده، با استفاده از اطلاعات پس‌زمینه (مانند محدودیت‌های سرعت) استفاده می‌کند. ما رابطه بین MM و عدم قطعیت را مطالعه می‌کنیم و الگوریتمی پیشنهاد می‌کنیم که کوتاه‌ترین مسیرهای k وزن‌دار را با منشورهای فضا-زمان ترکیب می‌کند.

3.1. مقدمه ای بر منشورهای فضا-زمان

اغلب، در کاربردهای عملی، بیشتر از برخی نقاط نمونه (مثلاً جمع آوری شده با GPS) در مورد مسیرهای اندازه گیری شده شناخته شده است.

(t_{i}, x_{i}, y_{i})

i = 1, 2, . . ., N

. به عنوان مثال، دانش پس زمینه، مانند محدودیت سرعت فیزیکی یا قانونی

v_{i}

در محل

(x_{i}, y_{i})

، ممکن است در دسترس باشد. چنین محدودیت سرعتی حتی ممکن است وابسته به زمان باشد، به عنوان مثال، برخی از خیابان ها ممکن است محدودیت سرعت متفاوتی در طول روز و شب یا در ساعات شلوغی داشته باشند. محدودیت‌های سرعتی که بین دو نقطه نمونه متوالی وجود دارد می‌تواند برای مدل‌سازی عدم قطعیت مکان MO بین نقاط نمونه استفاده شود. برای مدلسازی عدم قطعیت، Pfoser و Jensen [ 30 ] و بعدا، Egenhofer و همکاران. [ 31 و 32 ] مفهوم دانه ها را در ادبیات MOD معرفی کرد. قبلاً، ولفسون از سیلندرها برای مدلسازی عدم قطعیت [ 33 ] استفاده می کرد (همچنین به [ 3 ] مراجعه کنید). مهره ها قبلاً در جغرافیای زمانی هاگرستراند در دهه 1970 با نام منشورهای فضا-زمان شناخته شده بودند [ 34] .]. در این مقاله از این نام سنتی تر استفاده می کنیم. در حوزه GIS، منشورهای فضا-زمان نیز توسط میلر [ 35 ] مورد مطالعه قرار گرفتند.

منشور فضا-زمان بین دو نقطه نمونه متوالی به عنوان مجموعه ای از نقاط زمانی-مکانی که MO ها می توانستند از آنجا عبور کنند، با توجه به محدودیت سرعت (محلی) تعریف می شود. حالا ما این را رسمی تر می کنیم. فرض کنید S یک نمونه مسیر (اندازه گیری شده) باشد

{(t_{0}, x_{0}, y_{0}), (t_{1}, x_{1}, y_{1}), . . ., (t_{N}, x_{N}, y_{N})}

، با

t_{0} < t_{1} < \dots < t_{N}

. در مدل منشور فضا-زمان، برای هر جفت

(t_{i}, x_{i}, y_{i}), (t_{i + 1}, x_{i + 1}, y_{i + 1})

، با

0 \leq i < N

، در نمونه S ، منشور فضا-زمان مربوطه به مقدار حداکثر سرعت بستگی دارد

v_{i}

MO بین آن دو مکان. ما می دانیم که با توجه به محدودیت سرعت

v_{i}

، در زمان t

t_{i} \leq t \leq t_{i + 1}

، فاصله جسم تا

(x_{i}, y_{i})

حداکثر است

v_{i} (t - t_{i})

، و فاصله آن تا

(x_{i + 1}, y_{i + 1})

حداکثر است

v_{i} (t_{i + 1} - t)

. بنابراین مکان فضایی جسم جایی در تقاطع دیسک با مرکز است

(x_{i}, y_{i})

و شعاع

v_{i} (t - t_{i})

و دیسک با مرکز

(x_{i + 1}, y_{i + 1})

و شعاع

v_{i} (t_{i + 1} - t)

. بنابراین می توان گفت که منشور فضا-زمان از تمام نقاط تشکیل شده است

(t, x, y)

در فضای زمانی-مکانی که سه قید زیر را برآورده می کند:

t_{i} \leq t \leq t_{i + 1}

;

{(x - x_{i})}^{2} + {(y - y_{i})}^{2} \leq v_{i}^{2} {(t - t_{i})}^{2}

{(x - x_{i + 1})}^{2} + {(y - y_{i + 1})}^{2} \leq v_{i}^{2} {(t - t_{i + 1})}^{2}

. از نظر هندسی، دو معادله آخر، همانگونه که در شکل 2 نشان داده شده است، تقاطع یک مخروط رو به بالا و پایین را در فضای زمان-فضا تعریف می کنند . زنجیره ای از منشورهای فضا-زمان که نقاط نمونه مسیر متوالی را به هم متصل می کند، زنجیره منشور فضا-زمان نامیده می شود. گاهی اوقات، اصطلاح مهره برای منشور فضا-زمان و گردنبند خط زندگی برای زنجیره منشور فضا-زمان استفاده می شود [ 31 ]. برای جزئیات بیشتر در مورد خواص هندسی منشورهای فضا-زمان، به [ 36 ] مراجعه می کنیم.

3.2. استفاده از منشورهای فضا-زمان برای تطبیق نقشه

سهم اصلی این مقاله یک الگوریتم جدید MM است که از ترکیبی از تکنیک‌ها برای مدیریت عدم قطعیت در پایگاه‌های داده مسیر استفاده می‌کند. به‌طور دقیق‌تر، پیشنهاد می‌کنیم از منشورهای فضا-زمان در ترکیب با الگوریتم‌های K- کوتاه‌ترین مسیرها استفاده کنیم. برای ترکیب موثر منشورهای فضا-زمان در الگوریتم‌های خود، از برخی ساده‌سازی‌های هندسی استفاده می‌کنیم. طرح ریزی یک منشور فضا-زمان بر روی جزء فضایی دوبعدی فضا-زمان یک بیضی با نقاط کانونی است.

(x_{i}, y_{i})

(x_{i + 1}, y_{i + 1})

و محور نیمه اصلی

\frac{v_{i} (t_{i + 1} - t_{i})}{2} .

با این حال، برای کارایی و بیان آسان در SQL، ما یک کادر محدود از این بیضی را محاسبه می کنیم (با توجه به محورهای x – و y ). بخش‌های زیر به ترتیب چگونگی تعیین این جعبه مرزی طرح یک منشور فضا-زمان و نحوه استفاده از آن در عمل را توضیح می‌دهند.

3.2.1. محاسبات پروجکشن منشور فضا-زمان و جعبه مرزی آن

ما جعبه مرزی بیضی را، یعنی طرح فضایی یک منشور فضا-زمان در صفحه، به عنوان کوچکترین مستطیل، با اضلاع موازی با محورهای x – و y – که بیضی را محصور می کند، تعریف می کنیم . از طرف دیگر، می‌توان گفت که جعبه مرزی یک بیضی، مستطیلی است که حاصلضرب دکارتی برآمدگی بیضی روی محور x ، با برآمدگی بیضی روی محور y است . قضیه در این بخش نشان می دهد که چگونه می توان با توجه به نقاط کانونی جعبه مرزی یک بیضی در صفحه را تعیین کرد.

(x_{1}, y_{1})

(x_{2}, y_{2})

بیضی و محور نیمه اصلی آن

L > 0

. در این قضیه، مقادیر x دو طرف عمودی چپ و راست جعبه مرزی را می نامیم .

X_{1}

X_{2}

و مقادیر y دو طرف افقی پایین و بالای جعبه مرزی،

Y_{1}

Y_{2}

. بنابراین، جعبه مرزی بیضی (مرز) مجموعه است

[X_{1}, X_{2}] \times [Y_{1}, Y_{2}] .

برای اثبات این قضیه به پیوست A مراجعه می کنیم . اگرچه این قضیه کاملاً ابتدایی است، اما در کتاب‌های درسی، معمولاً فقط مواردی را می‌توان یافت که محورهای بیضی با محورهای مختصات موازی باشند. شکل A1 در ضمیمه A تصویری از یک بیضی و کادر محدود کننده آن را نشان می دهد.

قضیه 1.

اجازه دهید $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ نقاط (که نشان دهنده کانون ها است) در $R^{2}$ ، و اجازه دهید $L > 0$ یک عدد واقعی باشد (که نشان دهنده محور نیمه اصلی است). اجازه دهید $(x_{c}, y_{c})$ نقطه وسط کانون باشد و $d_{f}$ فاصله بین آنها باشد. اگر $x_{1} \neq x_{2}$ ، جعبه مرزی $[X_{1}, Y_{1}] \times [X_{2}, Y_{2}]$ از رابطه زیر بدست می آید:

$X_{1} = x_{c} - \sqrt{\frac{s^{2} ℓ^{2} + L^{2}}{1 + s^{2}}},$ $Y_{1} = y_{c} - \sqrt{\frac{s^{2} L^{2} + ℓ^{2}}{1 + s^{2}}},$
$X_{2} = x_{c} + \sqrt{\frac{s^{2} ℓ^{2} + L^{2}}{1 + s^{2}}},$ $Y_{2} = y_{c} + \sqrt{\frac{s^{2} L^{2} + ℓ^{2}}{1 + s^{2}}},$

جایی که $ℓ = \frac{1}{2} \sqrt{4 L^{2} - d_{f}^{2}}$ (محور نیمه فرعی) و $s = \frac{y_{1} - y_{2}}{x_{1} - x_{2}} .$ اگر $x_{1} = x_{2}$ ، سپس $X_{1} = x_{c} - ℓ$ ، $X_{2} = x_{c} + ℓ$ ، $Y_{1} = y_{c} - L$ و $Y_{2} = y_{c} + L$ (با $L = ℓ$ اگر $y_{1} = y_{2}$ ). ☐

3.2.2. استفاده از جعبه‌های مرزی پروجکشن منشورهای فضا-زمان در تطبیق نقشه

اکنون، ما دو مثال می‌آوریم که چگونه جعبه مرزی طرح منشور فضا-زمان می‌تواند به محدود کردن تعداد بخش‌های جاده‌ای که باید در فرآیند MM در نظر گرفته شوند کمک کند. اجازه دهید ابتدا نحوه مدل سازی شبکه های جاده ای را توضیح دهیم.

تعریف 1.

یک شبکه جاده ای

RN

یک نمودار است که در آن تعبیه شده است

R^{2}

یک گراف برچسب دار (جهت دار) که توسط مجموعه محدودی از رئوس ارائه می شود

V = {(x_{i}, y_{i}) \in R^{2} ∣ i = 1, \dots, N}

و مجموعه ای از لبه ها

E \subseteq V \times V

که دارای برچسب محدودیت سرعت هستند. رئوس در آن تعبیه شده است

R^{2}

توسط نقاطی که مختصات خود را دارند و یال ها به صورت پاره خط مستقیم بین رئوس تعبیه شده قرار می گیرند. این تعبیه‌های لبه ممکن است برای مدل‌سازی پل‌ها و تونل‌ها با هم قطع شوند. این بخش های خط مستقیم را بخش جاده می نامند. ☐

سمت چپ شکل 3، جعبه مرزی یک منشور فضا-زمان را نشان می دهد که برای دو نقطه A و B محاسبه شده است که 13 متر از هم فاصله دارند. منشور فضا-زمان در این مورد بسیار بزرگ است، زیرا مسافت طی شده از A تا B 35 ثانیه است (احتمالاً به دلیل ترافیک). طرح منشور فضا-زمان منطقه‌ای را نشان می‌دهد که ماشین می‌توانست در آن قرار داشته باشد، زمانی که به مدت 35 ثانیه با حداکثر سرعت بزرگراه (120 کیلومتر در ساعت) حرکت می‌کرد. این منجر به یک جعبه مرزی بزرگ از طرح یک منشور فضا-زمان می شود که شامل خیابان های زیادی است. از طرف دیگر، سمت راست شکل 3طرح ریزی یک منشور فضا-زمان را برای دو نقطه A و نشان می دهد

B,

که 11 متر از هم فاصله دارند و زمان سفر آنها یک ثانیه است. در اینجا، جعبه مرزی طرح منشور فضا-زمان تنها شامل دو بخش جاده است. این مثال‌ها نشان می‌دهند که چگونه استفاده از منشورهای فضا-زمان برای هرس کردن خیابان‌ها یا بخش‌های جاده‌ای که باید در فرآیند MM در نظر گرفته شوند، می‌تواند متفاوت باشد. در مثال دوم، سود بسیار بیشتر از مثال اول است.

استفاده از جعبه مرزی طرح منشور فضا-زمان، به جای خود بیضی، انگیزه عملی دارد. در پایان، شبکه های جاده ای با استفاده از گزاره در پایگاه داده های GIS ذخیره می شوند $POINT (x, y)$ ، که توسط OpenGIS در قالب متن شناخته شده استاندارد شده است. برای تأیید اینکه یک نقطه شبکه جاده در کادر مرزی قرار دارد $[X_{1}, Y_{1}] \times [X_{2}, Y_{2}]$ ، از پرس و جوی SQL زیر می توان استفاده کرد:

انتخاب کنید راس از جانب شبکه جاده ای جایی که ایکس 1 \leq رأس . ایکس و رأس . x \leq ایکس 2 و Y 1 \leq رأس . y و رأس . y \leq Y 2

این پرس و جو به دلیل شاخص فضایی در رئوس در یک شبکه جاده ای ساده و کارآمد است.

3.2.3. الگوریتمی برای مسیریابی k -کوتاهترین مسیر

این بخش را با توضیح مسیریابی k -shorttest path، که در زمینه شبکه ها شناخته شده است و در ادامه از آن استفاده می کنیم، شروع می کنیم. این نه تنها کوتاه ترین مسیر را بین دو نقطه پیدا می کند، بلکه همچنین

k - 1

مسیرهای دیگر به ترتیب افزایش هزینه در اینجا، k پارامتری است که تعداد کوتاه ترین مسیرهایی را که باید پیدا شود را نشان می دهد. برای اهداف ما، الگوریتم ین را برای رتبه بندی کوتاه ترین مسیرهای بدون حلقه k [ 4 ] تطبیق می دهیم. این الگوریتم ابتدا کوتاهترین مسیر بین دو راس را با استفاده از

A^{*}

-الگوریتم [ 37 ]. سپس، راس n-امین را در کوتاه ترین مسیر، با شروع می گیرد

n = 1

و افزایش n تا زمانی که

n = k - 1

و کوتاه ترین مسیر را از راس n تا راس انتهایی محاسبه می کند که مسیر خار نامیده می شود. مسیر از راس شروع به راس n- ام را مسیر ریشه می گویند. دو محدودیت بر روی یک مسیر خار یک راس اعمال می شود: (الف) نباید از هیچ راسی در مسیر ریشه آن راس عبور کند (برای اطمینان از اینکه مسیرها بدون حلقه هستند). و (2) نباید از راس جاری در هیچ لبه ای که توسط یک K -کوتاه ترین مسیر که قبلاً پیدا شده بود منشعب شود. شرط دوم به این معنی است که مسیر خار نمی تواند با لبه ای شروع شود که قبلاً در کوتاه ترین مسیر پیدا شده است. مثلاً اگر قبلاً کوتاه ترین مسیرها را پیدا کرده باشیم

A \to B \to C \to D

A \to B \to E \to F \to D

، و داریم

A \to B

به عنوان یک مسیر ریشه فعلی، پس ما نمی توانیم از لبه ها استفاده کنیم

B \to C

یا

B \to E

، زیرا اینها منجر به یک مسیر از قبل پیدا شده می شود. اگر یک مسیر خار جدید پیدا شود، به مسیر ریشه آن راس اضافه می شود تا یک مسیر کامل از ابتدا تا انتهای راس تشکیل شود. مثال 1 استفاده از الگوریتم ین را نشان می دهد.

مثال 1.

شبکه راه های شکل 4 را در نظر بگیرید و فرض کنید که تمام بخش های جاده (فلش ها) به یک اندازه وزن دارند. ما می خواهیم کوتاه ترین مسیر را از A تا D پیدا کنیم. واضح است که کوتاه ترین مسیر است

A \to B \to C \to D

، بنابراین این مسیر را در مسیر نتیجه قرار می دهیم. اکنون، ما به دنبال مسیرهای دیگری هستیم که از کوتاه ترین آنها شروع می شود. ما با مسیر ریشه A شروع می کنیم و به دنبال مسیری از A تا D می گردیم که قبلاً در لیست نتایج وجود ندارد. تنها مسیر ممکن، بدون احتساب لبه A تا B، این است

A \to E \to F \to G \to H \to D .

ما این مسیر را به لیست نتایج اضافه می کنیم (که اکنون نتیجه آن خواهد بود

k = 2

). در حال حاضر، ما با شروع

A \to B

به عنوان مسیر ریشه جدید و پیدا کنید

A \to B \to F \to G \to H \to D .

اینها همه مسیرهای ممکن هستند و الگوریتم به پایان می رسد. ☐

چندین مورد خاص از ورودی های MM وجود دارد که تنها با استفاده از الگوریتم کوتاه ترین مسیر، رسیدگی به آنها دشوار است. به عنوان مثال، شکل 5 یک MO را نشان می دهد که جاده نشان داده شده در خطوط باریک را دنبال کرده است (سه نقطه نمونه نشان داده شده است). الگوریتم‌های مبتنی بر محاسبه کوتاه‌ترین مسیر احتمالاً جاده خط ضخیم را انتخاب می‌کنند (با رنگ قرمز نشان داده شده است). ما این مسئله را مسئله مثلث می نامیم. به عنوان مثال، فرض کنید که امتیازهای 6، 5 و 6 به ترتیب به بخش های جاده 1، 2 و 3 داده می شود. الگوریتم Dijkstra بین بخش ها تصمیم می گیرد

1 + 2

و 3 را انتخاب کنید و بخش 3 را انتخاب کنید (بخشی که کمترین امتیاز را دارد)، اگرچه می دانیم که مسیر

1 + 2

مسیر تطبیق واقعی است. ما این را با تغییر دادن الگوریتم Dijkstra برای انتخاب مسیر با بالاترین امتیاز، با کار با تقسیم بر نمره کل یک مسیر، به جای استفاده از نمره کل، حل می کنیم. در بخش 3.2.4 ، نحوه حل این مسئله را با اختصاص وزن (محاسبه شده) به هر بخش جاده مورد بحث قرار می دهیم.

محاسبه مسیرهای خار از هر راس دارای پیچیدگی است

O (N)

و با استفاده از الگوریتم کوتاه ترین مسیر Dijkstra [ 38 ]،

O (N^{2} + | E |)

با

| E |

تعداد بخش جاده (لبه). را

A^{*}

-الگوریتم دارای یک

O (N^{2})

محدودیت پیچیدگی زمانی بالا از آنجایی که پیچیدگی زمانی برای هر دو الگوریتم Dijkstra و

A^{*}

-الگوریتم است

O (N^{2})

و در بدترین حالت، باید آن را برای تمام N راس محاسبه کنیم، به دست می آوریم

O (N^{3})

به عنوان پیچیدگی الگوریتم

3.2.4. شرح الگوریتم تطبیق نقشه منشورهای فضا-زمان

اکنون، نشان می‌دهیم که چگونه می‌توانیم از الگوریتم k – کوتاه‌ترین مسیر استفاده کنیم و با استفاده از مفهوم منشورهای فضا-زمان (معرفی شده در بخش 3.1 ) و با اضافه کردن وزن به یال‌ها، به عنوان مثال، از مشکلاتی مانند شکل 5 اجتناب کنیم. در شبکه راه علاوه بر این، منشورهای فضا-زمان به ما اجازه می دهند از مجموعه داده هایی استفاده کنیم که حاوی مقادیر پرت هستند، زیرا وزنی که لبه های مرتبط در چنین مواردی دریافت می کنند ناچیز است. ابتدا، الگوریتم بخش‌های جاده را که نزدیک‌ترین نقاط به نقاط نمونه فضا-زمان ثبت شده را محاسبه می‌کند، به شرح زیر است. همانطور که در بخش 3.2 توضیح داده شد، برای هر دو نقطه متوالی فضا-زمان، کادر مرزی طرح منشور فضا-زمان آنها را محاسبه می کنیم.. سپس، به بخش جاده وزن می دهیم، به گونه ای که نزدیک ترین بخش جاده به یک نقطه نمونه فضا-زمان معین، وزن m را دریافت می کند ، که m تعداد بخش های جاده ای است که می خواهیم به آن وزن دهیم. دومین بخش جاده نزدیک وزن خواهد داشت

m - 1,

تا نزدیکترین قطعه جاده که وزن یک را دریافت می کند، ادامه می دهیم . یادآور می‌شویم که فقط بخش‌های جاده‌ای که در جعبه محدود شده در نظر گرفته می‌شوند، از درج جاده‌هایی که احتمال رعایت آنها بسیار کم است، اجتناب می‌شود. در نهایت، k- کوتاه ترین مسیرها و همچنین وزن کل هر مسیر محاسبه می شود. مسیر با بیشترین وزن به عنوان مسیر مطابق با نقشه انتخاب می شود.

مثال 2.

نمونه ای از این الگوریتم، با حداکثر وزن سه، در جدول 1 و شکل 6 آمده است . در ادامه نحوه عملکرد الگوریتم را شرح می‌دهیم، با این فرض که منشورهای فضا-زمان قبلاً محاسبه شده‌اند (یعنی می‌دانیم کدام یال‌ها مرتبط هستند). شروع از نقطه

A

با توجه به نزدیکی قطعه به این نقطه به هر قطعه جاده وزنی اختصاص می دهیم. بنابراین، بخش جاده با

i d = 1

نمره سه دریافت می کند و بخش های جاده با

i d = 3

i d = 4

به ترتیب وزن های دو و یک را دریافت کنید. این وزن ها را می توان در ستون سوم جدول 1 (یعنی وزن برای هر بخش و نقطه A) یافت. بدین ترتیب،

A

احتمالاً با بخش جاده مطابقت دارد

i d = 1

. در مرحله بعد، نقطه B را در نظر می گیریم که وزن آن 3 است (برای قطعه با

i d = 4

، 2 (برای بخش 1) و 1 (برای بخش 3)، با توجه به نزدیکی نقطه B به آن بخش ها. وزن کل برای بخش های 1، 3 و 4 به ترتیب 5 خواهد بود (یعنی

3 + 2

) 3 (یعنی

2 + 1

) و 4 (یعنی

1 + 3

). از آنجایی که بخش 1 از سایر نقاط دورتر است (با در نظر گرفتن سه به عنوان حداکثر وزن)، وزن این بخش به عنوان پنج باقی می ماند. به همین ترتیب ادامه می دهیم تا همه نکات آنالیز شده و وزن ها تعیین شود. جدول 1 نتیجه الگوریتم وزن دهی را نشان می دهد. ستون سمت راست وزن کل هر بخش را نشان می دهد. بیایید فرض کنیم که ما انتخاب کرده ایم

k = 2

. با توجه به وزن های محاسبه شده در بالا، اکنون دو کوتاه ترین مسیر را محاسبه می کنیم. اولین راهی که به دست می آوریم این است

1 \to 4 \to 10 \to 11 \to 16

; دومی است

1 \to 3 \to 5 \to 10 \to 11 \to 16 .

اگرچه دومی لبه های بیشتری دارد، اما وزن کل آن (44) کوچکتر از وزن اولی (46) است، که در واقع مسیر واقعی MO است. توجه داشته باشید که این وزن به عنوان مجموع وزن های بخش های درگیر محاسبه می شود (یعنی

5 + 7 + 13 + 12 + 9 = 46

). ☐

به طور خلاصه، الگوریتم MM ما به شرح زیر است:

مرحله 1.: بخش‌های مربوطه شبکه جاده‌ای را با محاسبه برای هر جفت نقطه متوالی، انتخاب کنید که MO می‌توانست روی کدام بخش‌های جاده حرکت کند (با استفاده از جعبه‌های مرزی پیش‌بینی منشورهای فضا-زمان، همانطور که در بخش 3.2 توضیح داده شد ) .
گام 2.: برای هر نقطه نمونه، نزدیکترین بخش جاده را محاسبه کنید، همانطور که در بخش 3.2.4 توضیح داده شد ، و امتیازهایی را به هر بخش جاده اختصاص دهید. یک امتیاز برای یک بخش s با جمع کردن وزن تمام بخش هایی که با s مطابقت دارند محاسبه می شود .
مرحله 3.: در داخل شبکه جاده محدود تعیین شده در مرحله 1، k- کوتاه ترین مسیرها را محاسبه کنید و به عنوان خروجی، کوتاه ترین مسیر را با حداکثر وزن کل انتخاب کنید. اگر دو مسیر با وزن یکسان بدست آوریم، مسیر اول انتخاب می شود.

یادآور می‌شویم که گاهی اوقات، صرفاً اتخاذ یک راس شروع و پایان از بخش‌های جاده به ترتیب به اولین و آخرین نقطه زمان-فضا، ممکن است به تطابق صحیح منجر نشود. این در شکل 7 نشان داده شده است . در اینجا، بخش جاده نزدیک به

p 1

خواهد بود

R 1

، اگرچه مسیر به وضوح دنبال می شود

R 2

. نقطه پایان مطابقت داده خواهد شد

R 2

، در نهایت از یافتن مسیری برای این مسیر جلوگیری می کند. برای حل این مشکل و با در نظر گرفتن اینکه حداکثر خطای اندازه گیری حدود 10 متر است، الگوریتم به تمام بخش های شروع ممکن (به جای تنها یک) در یک دایره با شعاع پنج متر در اطراف اولین نقطه زمانی-فضا نگاه می کند. و تمام بخش های جاده ای را که با این دایره تلاقی می کنند انتخاب می کند. همین رویه برای قسمت انتهایی نیز دنبال می شود. سپس، الگوریتم به دنبال k- کوتاه ترین مسیرهای ممکن بین تمام بخش های شروع ممکن و بخش های پایانی در این مرزها (یعنی دایره ها) می گردد.

4. ارزیابی بهبود یافته الگوریتم های تطبیق نقشه

در بخش 2 ، ما مرتبط ترین الگوریتم های MM را در ادبیات مورد بحث قرار دادیم. در این بخش، روش جدیدی برای مقایسه دقیق عملکرد چنین الگوریتم‌هایی در برابر یکدیگر ارائه می‌کنیم. ما ابتدا منابع داده و ویژگی‌ها را مورد بحث قرار می‌دهیم، و سپس، معیارهای دقتی را که معمولاً برای ارزیابی نتایج الگوریتم‌های MM استفاده می‌شوند، ارائه می‌کنیم.

4.1. منابع و ویژگی های داده

در میان منابع داده‌ای که برای اعمال الگوریتم‌های MM استفاده می‌شود، ما این موارد را داریم: (الف) داده‌های برچسب‌گذاری شده توسط انسان (این موردی است که فرد خودش را شناسایی می‌کند، با انجام یک MM دستی که می‌توان آن را 100٪ درست در نظر گرفت). (ب) داده های تولید شده توسط رایانه (به دست آمده از روش های خودکار)؛ و (ج) داده های منبع ناشناخته.

برای روش (ب)، به عنوان مثال، با استفاده از یک شبکه جاده ای موجود، به طور تصادفی دو گره را در این شبکه انتخاب می کنیم و با استفاده از الگوریتم k – کوتاه ترین مسیر، kمسیرها ایجاد می شود. از این مجموعه مسیرها، یکی به طور تصادفی انتخاب شده و به عنوان مسیر واقعی تولید شده توسط یک MO انتخاب می شود. نمونه مسیر با تولید نقاط نزدیک به بخش جاده (در یک فاصله معین) تولید می شود. تعداد این نقاط بر اساس نرخ نمونه گیری انتخاب شده است. این روش در پیاده سازی ما استفاده می شود. برای روش (c)، ممکن است اتفاق بیفتد که مسیر واقعی دنبال شده برای یک نمونه مسیر مشخص نباشد. با توجه به اینکه، برای ارزیابی یک الگوریتم MM خاص، به تطبیق «صحیح» نیاز داریم، می‌توانیم با استفاده از الگوریتم MM دیگری برچسب‌گذاری صحیح را ایجاد کنیم. با توجه به اینکه دقت این الگوریتم دوم نیز مشخص نیست، نتایج به دست آمده از مقایسه الگوریتم اول با دوم ممکن است نادرست بوده و معنای محدودی داشته باشد.

الگوریتم های MM به ویژگی های نمونه های مورد استفاده به عنوان ورودی بسیار حساس هستند. در میان این ویژگی‌ها، موارد زیر را در نظر خواهیم گرفت: (الف) نرخ نمونه‌برداری (تعداد متوسط نقاط فضا-زمان در هر ثانیه از یک نمونه مسیر). ب) طول جاده؛ ج) خطاهای نمونه برداری (در نقاط یا به دلیل نویز در نمونه)؛ (د) طول مسیر؛ (ه) تراکم جاده (تعداد بخش های جاده در هر منطقه از نقشه).

4.2. روش‌هایی برای اندازه‌گیری کیفیت الگوریتم تطبیق نقشه

روش‌های متعددی برای اندازه‌گیری درستی یا دقت الگوریتم MM در یک نمونه مسیر معین در یک شبکه جاده‌ای معین وجود دارد. در زیر مهمترین آنها را فهرست می کنیم.

1. دقت بر اساس طول: این اندازه گیری (نگاه کنید به [ 21 ]) به عنوان طول کل بخش های جاده ای که به درستی تطبیق داده شده اند تقسیم بر طول کل مسیر منطبق محاسبه می شود. می بینیم که یک جاده طولانی (به معنای خطای بزرگ) مهمتر از یک جاده کوتاه است.

2. دقت بر اساس عدد: این روش (نگاه کنید به [ 21 ]) از تعداد بخش های جاده که به درستی تطبیق داده شده اند استفاده می کند. بنابراین، عدم تطابق یک بخش جاده طولانی مانند عدم تطابق یک بخش جاده کوتاه در نظر گرفته می شود. به عنوان تعداد بخش های جاده ای که به درستی تطبیق داده شده اند تقسیم بر تعداد بخش های جاده در مسیر منطبق محاسبه می شود. این روش زمانی به خوبی کار می‌کند که تعداد بخش‌های تطبیق صحیح مهم‌تر از طول مطابقت صحیح باشد، به عنوان مثال، الگوریتمی با دقت بالا بر اساس تعداد برای اعمال در مرکز شهر مناسب است.

3. دقت بر اساس طول منهای جاده اشتباه: این روش (نگاه کنید به [ 2 ]) از طول کل بخش های جاده که به اشتباه اضافه و حذف شده اند استفاده می کند. از نظر طول دارای همان مزایای دقت است. تفاوت اصلی این است که بخش های جاده ای که به اشتباه اضافه شده اند جریمه بیشتری دارند. از آنجایی که این اندازه گیری به ما ایده ای درباره دقیق بودن مسیر محاسبه شده نمی دهد، آن را با دقت اندازه گیری طول ترکیب می کنیم و فرمول زیر را برای دقت بر اساس طول منهای جاده اشتباه می دهیم: مقدار را می گیریم:

طول از به درستی تطبیق جاده بخش ها - د - - د + جمع طول از را تطبیق خط سیر ،

اگر این مقدار مثبت باشد و صفر را بگیریم در غیر این صورت.

4. فاصله فرشه ضعیف، متوسط و قوی: این روش [ 11 ، 12 ] از اندازه گیری فاصله فرشه بین دو منحنی استفاده می کند. میانگین فاصله فرشت میانگین فواصل فرشت ضعیف و قوی است که در بخش 2 توضیح داده شده است . یکی از مزایای استفاده از روش فاصله فرشه این است که به جای نگاه کردن به بخش های جاده، به خود منحنی نگاه می کنیم. یک مسیر منطبق ممکن است دقت پایینی با سایر معیارها داشته باشد، اما همچنان می تواند بسیار نزدیک به مسیر واقعی باشد. استفاده از این روش فاصله به ما امکان می دهد محاسبه کنیم که این مسیرها چقدر نزدیک هستند. با این حال، می‌توانیم برای مسیری که هیچ بخش جاده مشترکی با مسیر اصلی ندارد (به عنوان مثال، یک مسیر موازی) امتیاز دقت بالایی کسب کنیم. A را فرض کنید و راB دو منحنی هستند. فاصله Fréchet به طور رسمی به این صورت تعریف می شود:

اف (الف ، ب) = inf α ، β حداکثر t ϵ [0, 1] {د (A (α (t)) ، B (β (t)))},

که در آن reparametrizations $α, β : [0, 1] \to [0, 1]$ A و B جراحي‌هاي پيوسته و بدون كاهش هستند. در فرمول فوق، d تابع فاصله اقلیدسی استاندارد است. فاصله Fréchet ضعیف نیاز غیر کاهشی را حذف می کند.

4.3. مشکلات در اندازه گیری دقت

روش های فوق در تنظیمات خاصی از مشکلاتی رنج می برند. اولین مثال زمانی اتفاق می‌افتد که یک الگوریتم MM بخش‌های جاده نادرست را که موازی با مسیر واقعی هستند انتخاب می‌کند. دقت از نظر طول، دقت تعداد و طول معیارهای اشتباه کیفیت جاده هیچ امتیازی به بخش هایی که موازی با مسیر صحیح هستند یا حتی آن بخش ها را جریمه نمی کند. بنابراین، مسیرهای منطبق که موازی با مسیر صحیح هستند، اما هنوز بسیار نزدیک به آن هستند، امتیاز بسیار پایینی می گیرند. معیارهای کیفی که از فاصله منحنی بین مسیر صحیح و مسیر منطبق استفاده می‌کنند (مثلاً فاصله Fréchet) این مورد را بهتر انجام می‌دهند، زیرا به این موضوع توجه نمی‌کنند که کدام بخش جاده دقیقا مطابقت داشته است. از سوی دیگر، معیارهای کیفیت با استفاده از فاصله منحنی از مشکل دیگری رنج می‌برند که الگوریتم MM بخش‌های زیادی را انتخاب می‌کند (به عنوان مثال، علاوه بر هر بخش صحیح، یک بخش موازی به اشتباه انتخاب شده است). این باعث می شود که مسیر منطبق دو برابر مسیر صحیح باشد. معیارهای کیفیت با استفاده از فاصله منحنی به این مسیر امتیاز بالایی می‌دهد، زیرا هر بخش انتخاب شده یا روی منحنی درست است یا بسیار نزدیک به آن است. با این حال، این نادرست است، به دلیل تعداد زیادی از بخش های جاده ای که به اشتباه انتخاب شده اند. زیرا هر بخش انتخاب شده یا بر روی منحنی صحیح قرار دارد یا بسیار نزدیک به آن است. با این حال، این نادرست است، به دلیل تعداد زیادی از بخش های جاده ای که به اشتباه انتخاب شده اند. زیرا هر بخش انتخاب شده یا بر روی منحنی صحیح قرار دارد یا بسیار نزدیک به آن است. با این حال، این نادرست است، به دلیل تعداد زیادی از بخش های جاده ای که به اشتباه انتخاب شده اند.

4.4. اندازه گیری دقت جدید: CL-Accuracy

ما معیار کیفیت جدیدی را برای رسیدگی به مشکلات ذکر شده در بخش 4.3 پیشنهاد می کنیم . ما نقاط قوت برخی از اقدامات مورد بحث در بالا را ترکیب می کنیم. به طور خلاصه، فاصله منحنی بین مسیر صحیح و منطبق را محاسبه می کنیم و سپس طول هر دو مسیر را در نظر می گیریم. ما به این روش جدید دقت منحنی و طولی یا به اختصار CL-accuracy را نشان می دهیم.

برای محاسبه این اندازه گیری جدید، ابتدا امتیازی بین صفر تا 100 برای هر بخش انتخاب شده توسط الگوریتم MM محاسبه می کنیم. برای این کار، فاصله اقلیدسی را تا نزدیکترین قطعه در مسیر صحیح، با حداکثر 100 متر محاسبه می کنیم. این محدودیت بر اساس دقت دستگاه های GPS فعلی است (اگر نقطه ای بیش از 100 متر دورتر باشد، تقریباً به طور قطع یک نقطه پرت است). نمره کل برای مسیر منطبق با جمع کردن تمام امتیازات بخش و سپس با استفاده از فرمول زیر محاسبه می شود:

امتیاز = maxScore - امتیاز maxScore .

عبارت maxScore در فرمول فوق حداکثر امتیاز ممکن برای مسیر منطبق (100 برابر تعداد بخش ها) است. این فرمول امتیازی را برای فاصله منحنی بین مسیر صحیح و منطبق محاسبه می کند. یک نمره از $100 %$ به این معنی که هر بخش از مسیر منطبق بر مسیر صحیح است. یک نمره از $0 %$ به این معنی که هر قطعه 100 متر یا بیشتر از مسیر صحیح فاصله دارد. در مرحله بعد، طول هر دو مسیر را در نظر می گیریم و امتیاز بالا را در ضریب بین طول کوچکترین و بزرگترین مسیر ضرب می کنیم. اگر O مسیر اصلی و M نسخه مطابق نقشه آن باشد، O می تواند طولانی تر یا کوتاه تر از M باشد (بسته به الگوریتمی که استفاده می شود). از آنجایی که می‌خواهیم اندازه‌گیری تشابه را در محدوده 0% تا 100% بدست آوریم، اگر $| O | > | M |$ ، ما استفاده می کنیم $\frac{| M |}{| O |}$ بجای. در نتیجه، اگر، برای مثال، M باشد $10 %$ طولانی تر از O ، این دقیقاً به همان روشی جریمه می شود که اگر O بود $10 %$ طولانی تر از M. با این روش، یک مسیر منطبق که دو برابر طول مسیر صحیح است، فقط نصف امتیاز را می گیرد.

5. مقایسه تجربی الگوریتم های تطبیق نقشه

ما اکنون تعدادی آزمایش از الگوریتم‌های MM مختلف را بر روی مجموعه‌های داده نمونه مسیری ارائه می‌کنیم. هدف این است که مشخص شود کدام نوع الگوریتم MM بر روی یک نوع خاص از نمونه مسیر بهتر عمل می کند. ما تعدادی از الگوریتم‌های موجود را پیاده‌سازی کرده‌ایم و آنها را با الگوریتم MM مبتنی بر عدم قطعیت خود مقایسه کرده‌ایم (ارائه شده در بخش 3.2.4 ). ما الگوریتم‌هایی را از هر دسته‌ای که در آن بحث شده انتخاب کرده‌ایمما الگوریتم‌هایی را از هر دسته‌ای که در بخش 2، به منظور مقایسه رویکرد خودمان با نمایندگان هر دسته. الگوریتم‌هایی که برای دسته تحلیل هندسی انتخاب کردیم، الگوریتم منحنی به نقطه و الگوریتم منحنی به منحنی هستند، اما چند تغییر در آنها ایجاد کرده‌ایم: از الگوریتم Dijkstra زمانی استفاده می‌کنیم که دو بخش همسان متوالی به هم متصل نباشند. این تضمین می کند که هیچ شکافی در مسیر محاسبه شده وجود ندارد. ما الگوریتم گرینفلد را برای دسته تحلیل توپولوژیکی انتخاب کرده‌ایم، زیرا این یکی از اولین الگوریتم‌ها در نوع خود بود و بسیاری از الگوریتم‌های دیگر شبیه به این روش هستند. برای مقوله احتمالی، الگوریتم را توسط Ochieng، Quddus و Noland پیاده سازی کرده ایم. برای مقوله نرخ نمونه برداری پایین، ما الگوریتم تطابق ST را پیاده سازی کرده ایم [ 21]). در نهایت، منشورهای فضا-زمان خود را با الگوریتم k -shorttest paths نیز پیاده سازی کرده ایم. اگرچه برخی الگوریتم‌های جدیدتر پیشنهاد شده‌اند، اکثر آنها شواهد قطعی از اثربخشی ارائه نمی‌دهند، و ما معتقدیم (و این از ادبیات [ 5 ] نتیجه می‌گیرد) که الگوریتم‌هایی که انتخاب کرده‌ایم به اندازه کافی بالغ هستند و در طول زمان ثابت شده‌اند. برای موارد مختلف موثر است برای الگوریتم منشورهای فضا-زمان، در آزمایش‌ها، حداکثر وزن را (بر اساس آزمایش‌های انجام‌شده قبلی) در نظر گرفته‌ایم.

m = 50

k = 10

(توجه داشته باشید که k یک حد بالایی است، نه یک ثابت) و حداکثر سرعت 120 کیلومتر در ساعت.

در بخش 5.1 ، آزمایش‌های این الگوریتم‌ها را بر روی نمونه‌های مسیر تولید شده توسط یک دستگاه مجهز به GPS شرح می‌دهیم. در بخش 5.2 ، آزمایش‌ها را بر روی نمونه‌های خط سیر تولید شده توسط رایانه نشان می‌دهیم. در نهایت، در بخش 5.3 ، ما همه این نتایج را ترکیب کرده و یک نتیجه‌گیری را در مورد الگوریتم‌های MM مورد بحث تدوین می‌کنیم. تمام تست ها بر روی یک مک بوک با پردازنده 2.16 گیگاهرتزی اینتل Core 2 Duo و 1 گیگابایت رم انجام شد.

5.1. آزمایش بر روی داده های برچسب انسانی

برای آزمایش‌های روی داده‌های برچسب‌گذاری شده انسانی، ما با نمونه‌های مسیر تولید شده توسط یک دستگاه مجهز به GPS که به صورت دستی برچسب‌گذاری شده‌اند، کار کردیم. در این داده ها، مهرهای زمانی، سرعت و اطلاعات عنوان گنجانده شده است. داده های مورد استفاده برای این آزمون بیست نمونه مسیر از نیروی پلیس گنت بلژیک است. نمونه های مسیر در سطح شهر قرار گرفت و توسط خودروهای مداخله ای پلیس جمع آوری شد. هر نمونه شامل تقریباً 400 نقطه فضا-زمان است که طول آن حدود 4 کیلومتر است. آنها همچنین حاوی برخی از شکاف های داده هستند که معمولاً به دلیل رانندگی در تونل ها (جایی که دریافت GPS وجود ندارد) ایجاد می شود. در شکل 8 ، میانگین نتیجه را بر روی بیست نمونه مسیر از مجموعه داده پلیس نشان می دهیم. یک نمای کلی از میانگین زمان اجرا در جدول 2 آورده شده است.

در نگاه اول، الگوریتم های تجزیه و تحلیل هندسی بدترین عملکرد را دارند، که منطقی است، زیرا آنها به چیزی جز مکان نقطه فضا-زمان نگاه نمی کنند. اطلاعات مربوط به محل تطبیق نقاط قبلی یا نحوه اتصال شبکه جاده نادیده گرفته می شود. به نظر می رسد که سایر انواع الگوریتم ها همگی عملکرد مناسبی دارند. برای حالت متوسط، منشورهای فضا-زمان ما همراه با الگوریتم k -shorttest paths به نظر بهترین عملکرد را دارند. در بخش 5.2، ما تست های این الگوریتم ها را برای موارد مختلف آزمایشی مورد بحث قرار می دهیم تا بفهمیم کدام الگوریتم در چندین سناریو مختلف بهترین کار را دارد. زمان‌های اجرا برای همه الگوریتم‌های آزمایش‌شده مشابه است، اگرچه، البته، با توجه به سادگی آن، گرین‌فیلد بهترین عملکرد را به‌خاطر دقت دارد. به طور کلی، همه این الگوریتم‌ها می‌توانند در زمان واقعی روی یک برنامه‌ریز مسیر اجرا شوند. استثنا الگوریتم تطبیق ST (به طور متوسط 76 ثانیه) است که اگر نرخ نمونه برداری خیلی زیاد باشد، نمی توان آن را در زمان واقعی اجرا کرد. این یک نتیجه مورد انتظار است، همانطور که در بخش 2 توضیح دادیم ، با توجه به اینکه یک الگوریتم جهانی است.

ممکن است به نظر غیرشهودی به نظر برسد که الگوریتم‌های تحلیل هندسی کمی کندتر از بسیاری از الگوریتم‌های دیگر عمل می‌کنند. این به دلیل اصلاحاتی است که در این الگوریتم ها انجام داده ایم. در پیاده‌سازی الگوریتم‌های تحلیل هندسی، از الگوریتم کوتاه‌ترین مسیر Dijkstra زمانی استفاده می‌کنیم که دو بخش منطبق متوالی به هم متصل نباشند. این تضمین می کند که هیچ شکافی در مسیر محاسبه شده وجود ندارد. بدون این تغییر، این الگوریتم‌ها به طور قابل ملاحظه‌ای سریع‌تر از الان اجرا می‌شوند، اما همچنان نتایج بدتری دارند.

5.2. آزمایشات روی داده های تولید شده توسط کامپیوتر

در این بخش از داده های تولید شده توسط یک مولد نمونه مسیر استفاده می کنیم. با استفاده از این ژنراتور، می‌توانیم نمونه‌های مسیری با ویژگی‌های مختلف که در بخش 4 مورد بحث قرار گرفته‌اند تولید کنیم . ما مطالعه را به نرخ نمونه‌گیری بالا و پایین تقسیم می‌کنیم.

5.2.1. نرخ نمونه برداری بالا

در اینجا، اختلاف زمانی بین دو نقطه نمونه متوالی کمتر از 10 ثانیه است.

نمونه های مسیر شبیه سازی شده بدون خطای اندازه گیری

برای این آزمایش، نمونه‌هایی از مسیر با نقاط فضا-زمان که هر دو ثانیه یک بار و طول‌های چند کیلومتری ثبت می‌شوند، ایجاد کردیم. شکل 9 (سمت چپ) میانگین نتیجه را در ده مسیر تولید شده توسط کامپیوتر نشان می دهد. می‌بینیم که همانطور که انتظار می‌رفت، همه الگوریتم‌ها می‌توانند مسیر صحیح را به خوبی تشخیص دهند، به استثنای الگوریتم نقطه به نقطه، که بخش‌های زیادی را انتخاب کرد و در نتیجه امتیاز کمتری نسبت به بقیه کسب کرد. می توان گفت که سایر الگوریتم ها به اندازه کافی دقیق هستند که بتوان با این نوع داده ها استفاده کرد.

نمونه های مسیر شبیه سازی شده با خطاهای اندازه گیری

برای این آزمایش، نمونه‌های مسیری با نقاط فضا-زمان با فاصله زمانی بین سه تا ۱۰ ثانیه، با خطای بین صفر تا ۱۵ متر برای هر نقطه ایجاد کردیم. شکل 9 (سمت راست) میانگین نتیجه آزمایش را در ده مسیر نشان می دهد. الگوریتم‌هایی که از تحلیل هندسی استفاده می‌کنند در این مورد ضعیف عمل می‌کنند، زیرا بسیاری از مثبت‌های کاذب را تولید می‌کنند. انواع دیگر الگوریتم‌ها مانند داده‌ها بدون خطا عمل می‌کنند و به طور کلی مشکلی در رسیدگی به این خطاها ندارند.

نمونه های مسیر شبیه سازی شده با خطاهای اندازه گیری و نقاط پرت

داده‌های جمع‌آوری‌شده با یک دستگاه مجهز به GPS نه تنها می‌تواند حاوی خطاهای اندازه‌گیری باشد، بلکه می‌تواند حاوی مقادیر پرت نیز باشد. ما نمونه هایی را برای شبیه سازی این وضعیت تولید کردیم. شکل 10(سمت چپ) میانگین نتیجه را در ده نمونه مسیر با نرخ نمونه برداری بالا (سه تا 10 ثانیه بین نقاط فضا-زمان)، با خطاهای اندازه گیری (بین صفر تا 15 متر در هر نقطه) و با نقاط پرت (یک تا سه نقطه پرت در هر مجموعه داده) نشان می دهد. ، از 10 تا 250 متر بزرگ است). می‌توانیم ببینیم که الگوریتم‌های هندسی نمی‌توانند به خوبی با نقاط پرت رفتار کنند، زیرا آنها کوتاه‌ترین مسیر را بین هر یک از دو نقطه متوالی محاسبه می‌کنند و این مسیر را به مسیر محاسبه‌شده اضافه می‌کنند. بنابراین، بسیاری از بخش‌های جاده‌ای که به نقاط پرت منتهی می‌شوند، به اشتباه به محاسبه اضافه می‌شوند و در نتیجه امتیاز ضعیفی به دست می‌آیند. الگوریتم تطبیق ST روش مشابهی برای محاسبه مسیر دارد و همچنین دارای امتیاز ضعیف ناشی از این است. منشورهای فضا-زمان با الگوریتم k-shortest paths در این مورد بسیار خوب عمل می کنند و در آزمون فوق نمره کامل می گیرند.

نمونه های مسیر شبیه سازی شده با خطاها و شکاف های اندازه گیری

هنگام عبور از تونل ها، هیچ ارتباطی با ماهواره های GPS برای محاسبه مکان MO وجود ندارد و باعث ایجاد شکاف در نمونه های مسیر می شود. ما نمونه‌های مسیری با شکاف‌ها را برای شبیه‌سازی این وضعیت تولید کرده‌ایم و سپس آزمایش‌های خود را انجام دادیم. ما 10 نمونه مسیر با نرخ نمونه‌برداری بالا (سه تا 10 ثانیه بین نقاط)، خطاهای اندازه‌گیری (بین صفر تا 15 متر در هر نقطه) و شکاف‌ها (یک تا سه شکاف در هر نمونه، در اندازه‌های 50 تا 200 متر) تولید کردیم. میانگین نتیجه الگوریتم MM روی آن نمونه ها در شکل 10 (سمت راست) نشان داده شده است. به طور کلی، شکاف ها برای هیچ یک از الگوریتم ها مشکلی ایجاد نکردند، اگرچه تطبیق ST قادر به محاسبه یک مسیر برای دو مجموعه داده نبود. منشور فضا-زمان ما با k-الگوریتم کوتاهترین مسیرها و الگوریتم توسط Ochieng و همکاران. اینجا خیلی خوب عمل کرد

نمونه های مسیر شبیه سازی شده در بزرگراه با خطاهای GPS

برای این آزمایش، نمونه‌های مسیر را به جای نزدیک یا در یک شهر، در بزرگراه شبیه‌سازی کردیم. در بزرگراه، بخش‌های جاده‌ای ممکن کمتری وجود دارد که بتوان از بین آنها انتخاب کرد. شکل 11 (سمت چپ) میانگین نتایج را در ده نمونه مسیر شبیه سازی شده با نرخ نمونه برداری بالا (سه تا 10 ثانیه بین نقاط GPS)، با خطاهای اندازه گیری (بین صفر تا 15 متر در هر نقطه) نشان می دهد. امتیاز ضعیف اکثر الگوریتم ها را می توان با این واقعیت توضیح داد که الگوریتم ها اغلب جاده های موازی را انتخاب می کنند، همراه با جاده های غیر بزرگراهی نزدیک بزرگراه. مسیر واقعی یا یک مسیر موازی در هر مورد انتخاب شد، اما به دلیل انتخاب بسیاری از بخش‌های جاده نادرست، آنها همچنان نمره ضعیفی گرفتند. استثناهای این مورد منشور فضا-زمان با k است-کوتاه ترین مسیرها و الگوریتم احتمالاتی توسط Ochieng و همکاران، که بسیار خوب کار می کرد (الگوریتم دوم بهترین از همه است).

نمونه های مسیر شبیه سازی شده در مسافت طولانی با خطاهای اندازه گیری

مجموعه داده‌های مورد استفاده در این بخش تاکنون فقط شامل نمونه‌های مسیری با اندازه متوسط بودند. از آنجایی که برخی از الگوریتم‌های پیاده‌سازی شده افزایشی هستند، خطاهای ابتدای الگوریتم ممکن است تفاوت زیادی در محاسبات بعدی ایجاد کند. ما اکنون از نمونه های مسیری که حاوی چندین هزار نقطه فضا-زمان هستند استفاده می کنیم. میانگین نتیجه در ده نمونه مسیر با سرعت نمونه برداری بالا (سه تا 10 ثانیه بین نقاط فضا-زمان)، با خطاهای اندازه گیری (بین صفر تا 15 متر در هر نقطه) و چندین برابر نقاط فضا-زمان بیشتر از نمونه های قبلی است. در شکل 11 (سمت راست) نشان داده شده است. می بینیم که به طور کلی، همه الگوریتم ها در این مورد خوب عمل کردند.

تبصره 1.

ما خاطرنشان می‌کنیم که امتیاز ضعیف الگوریتم‌های احتمالی ناشی از این واقعیت است که الگوریتم هنگام انتخاب یک بخش جاده خاص گیر می‌کند، زیرا جایگزین امتیاز بسیار پایینی دارد و هرگز انتخاب نمی‌شود. با توجه به این مشکل، این الگوریتم بیشتر از این بخش جاده پیشرفت نمی کند. این باعث نمره بد می شود. در سایر آزمایشات چنین مشکلی مشاهده نشد.

5.2.2. نرخ نمونه برداری پایین

اکنون، نمونه هایی را مورد بحث قرار می دهیم که نقاط نمونه بسیار بیشتر از 10 ثانیه از هم فاصله دارند.

نمونه های مسیر شبیه سازی شده بدون خطای اندازه گیری

نمونه های مسیر مورد استفاده در این آزمایش از همان مسیری پیروی می کنند که در مورد مشابه در بخش 5.2.1 استفاده شده است . ما ده مسیر با نرخ نمونه برداری کم (60 تا 150 ثانیه بین نقاط متوالی فضا-زمان) و بدون خطای اندازه گیری تولید کردیم. نتایج در شکل 12 (سمت چپ) نشان داده شده است. همانطور که انتظار می رفت، الگوریتم تطبیق ST، که به طور خاص برای داده های MM با نرخ نمونه برداری پایین طراحی شده است، بهترین امتیاز را کسب می کند. الگوریتم های تحلیل هندسی و منشور فضا-زمان با الگوریتم k -shortest paths در اکثر موارد به خوبی کار می کنند. با این حال، زمانی که نرخ نمونه‌برداری به مقادیر بسیار پایین کاهش می‌یابد، منشور فضا-زمان با k-الگوریتم shorttest paths موفق به تولید مسیر نمی شود که در تست های ما دو بار اتفاق افتاده است. این موارد خاص در شکل نشان داده نشده‌اند، اما بر نتایج میانگین کلی تأثیر داشتند و در این مورد، نمودار در شکل 12 (سمت چپ) الگوریتم منشورهای فضا-زمان را جریمه می‌کند. الگوریتم گرینفلد و الگوریتم احتمالی بر روی داده ها با نرخ نمونه گیری پایین ضعیف عمل کردند. دلیل آن این است که این الگوریتم‌ها در هر نقطه فضا-زمان حداکثر یک قطعه جاده را انتخاب می‌کنند و بنابراین، بخش‌های جاده به اندازه کافی انتخاب نمی‌شوند.

نمونه های مسیر شبیه سازی شده با خطاهای اندازه گیری

در اینجا نیز نمونه های مسیر همان مسیری را دنبال می کنند که در مورد مشابه در بخش 5.2.1 استفاده شده است . ما ده نمونه مسیر با نرخ نمونه برداری کم (60 تا 150 ثانیه بین نقاط فضا-زمان) و با خطاهای اندازه گیری (بین صفر تا 15 متر در هر نقطه) تولید کردیم. شکل 12 (سمت راست) میانگین نتایج را نشان می دهد. می بینیم که ارائه خطاها در داده ها به نحوی مرتبط بر نتایج تأثیر نمی گذارد. الگوریتم تطبیق ST و الگوریتم تحلیل هندسی عملکرد بسیار خوبی دارند. برعکس، الگوریتم گرینفلد، منشور فضا-زمان با الگوریتم k -shorttest paths و الگوریتم احتمالی عملکرد ضعیفی دارند.

5.3. بحث

اکنون نتایج فوق را جمع بندی و جمع بندی می کنیم و به طور خلاصه بحث می کنیم که کدام الگوریتم در موقعیت های مختلف مناسب تر است. به عنوان یک نمای کلی، ما در شکل 13 میانگین خطاهای تطبیق همه آزمایشات روی مجموعه داده با نمونه های مسیر چندگانه را نشان می دهیم. در شکل 14 ، میانگین زمان اجرا در هر مورد و در ستون آخر، میانگین کلی را ارائه می دهیم.

در بیشتر موارد، الگوریتم‌های تحلیل هندسی (نقطه به نقطه و نقطه به منحنی) کمترین نتایج را به دست می‌دهند، اگرچه سریع‌تر از بقیه اجرا می‌شوند، زیرا این نوع الگوریتم به محاسبات کمتری نیاز دارد. این البته برای دستگاه هایی با قدرت پردازش پایین مرتبط است.

الگوریتم‌های احتمالی Ochieng، Quddus و Noland نیز تقریباً در هر مورد آزمایشی عملکرد خوبی داشتند. الگوریتم فقط با مسیرهای طولانی یا مسیرهایی با نرخ نمونه‌برداری پایین مشکل داشت و زمانی که داده‌ها در بزرگراه قرار می‌گیرند، به طور قابل‌توجهی بهتر از سایر الگوریتم‌ها عمل می‌کرد. الگوریتم تطبیق ST، الگوریتمی که به طور خاص برای داده‌هایی با نرخ نمونه‌گیری پایین ایجاد شده است، نتایج متفاوتی روی داده‌هایی با نرخ نمونه‌گیری بالا داشت. با توجه به این نتایج متفاوت و زمان طولانی مورد نیاز برای اجرای این الگوریتم، ما فکر می‌کنیم که باید از استفاده از آن بر روی داده‌هایی با نرخ نمونه‌برداری بالا اجتناب کرد. با این حال، برای داده‌هایی با نرخ نمونه‌گیری پایین، الگوریتم ثابت می‌کند که مطابقت بسیار نزدیک با مسیر را در یک زمان اجرای معقول محاسبه می‌کند.

الگوریتم فضا-زمان با k -shorttest paths الگوریتم در بیشتر موارد به خوبی کار می کند. این استثنا زمانی اتفاق می‌افتد که مقادیر پرت زیادی در داده‌ها وجود داشته باشد: به دلیل روشی که الگوریتم مسیر را محاسبه می‌کند، پرت‌ها باعث ایجاد وقفه‌های کوچک در محاسبه می‌شوند، که باعث می‌شود الگوریتم در هنگام مواجهه با نقطه پرت کند شود. همچنین در مواقعی که میزان نمونه برداری بسیار پایین است دچار مشکل می شود. با این حال، به طور کلی، منشور فضا-زمان با الگوریتم k -کوتاه‌ترین مسیرها با الگوریتم‌هایی که عملکرد خوبی دارند و در بسیاری از موارد از آنها بهتر عمل می‌کنند، رقابت می‌کند و همچنین در بسیاری از سناریوهای مختلف عملکرد معقولی را نشان می‌دهد. یادآور می‌شویم که حتی اگر تحت نرخ نمونه‌گیری داده‌ای بالا بهتر عمل کند، برای موقعیت‌های با نرخ نمونه‌گیری پایین نیز به خوبی کار می‌کند (اگر نرخ خیلی پایین نباشد).

6. نتیجه گیری و مسائل باز

ما یک الگوریتم جدید ارائه کرده‌ایم که عدم قطعیت نقاط نمونه در یک مسیر را برای حل مشکل MM ارائه می‌کند. استفاده از مفهوم منشورهای فضا-زمان، همراه با الگوریتم‌های وزنی k- کوتاه‌ترین مسیر، منجر به الگوریتمی می‌شود که علاوه بر کاربرد در طیف وسیعی از انواع نمونه مسیر، در بیشتر موارد از الگوریتم‌های شناخته شده MM بهتر عمل می‌کند. ما این ادعا را با اجرای آن الگوریتم‌ها و استفاده از روشی جدید برای اندازه‌گیری دقت الگوریتم MM پشتیبانی می‌کنیم.

از لحاظ تاریخی، ناحیه MM عمدتاً توسط نتایج تجربی هدایت می‌شود. الگوریتم‌ها اغلب با استفاده از آزمایش‌هایی بر روی مجموعه داده‌های انتخاب شده یا تولید شده به صورت موقت مقایسه می‌شوند. علاوه بر این، در زمینه MM، هیچ مخزنی از پیاده سازی های موجود وجود ندارد. بنابراین، در این مقاله، منشور فضا-زمان خود را با الگوریتم k -shortest paths با الگوریتم‌های MM موجود که خودمان پیاده‌سازی کرده‌ایم، مقایسه کرده‌ایم ، احتمالاً برخی بهینه‌سازی‌ها را از دست داده‌اند. بنابراین، ما معتقدیم که یک معیار کلی و انعطاف‌پذیر برای ارزیابی الگوریتم‌های MM وجود ندارد و یک هدف مناسب برای کار آینده است.

ضمیمه الف. محاسبات طرح ریزی یک منشور فضا-زمان و جعبه مرزی آن

قضیه در این بخش قضیه 1 را بسط می دهد. این نشان می دهد که چگونه جعبه مرزی

[X_{1}, Y_{1}] \times [X_{2}, Y_{2}]

یک بیضی در صفحه را می توان با توجه به نقاط کانونی تعیین کرد

(x_{1}, y_{1})

(x_{2}, y_{2})

از بیضی و محور نیمه اصلی

L > 0

از بیضی شکل A1 تصویری از یک بیضی و جعبه مرزی آن را نشان می دهد.

شکل A1.یک بیضی با نقاط کانونی

(x_{1}, y_{1})

(x_{2}, y_{2})

، محور نیمه اصلی L و محور نیمه کوچک ℓ (به رنگ قرمز). جعبه مرزی آن به رنگ آبی نشان داده شده است.

متذکر می شویم که محور اصلی،

2 L

، دو برابر طولانی ترین فاصله از مرکز بیضی تا نقطه ای از بیضی را بیان می کند. ما همچنین از عبارات محور اصلی و محور فرعی استفاده خواهیم کرد (به زیر مراجعه کنید) برای نشان دادن خطوط واقعی حامل این طول ها.

برای در نظر گرفتن طول عبارات، چند اختصار را معرفی می کنیم. مرکز بیضی نقطه است

(ایکس ج ، y ج) = (ایکس 1 + ایکس 2 2 ، y 1 + y 2 2) .

فاصله بین کانون ها به اختصار با $d_{f}$ ، به این معنا که

د f = (ایکس 1 - ایکس 2) 2 + (y 1 - y 2) 2 ——————\sqrt .

محور نیمه فرعی بیضی با ℓ نشان داده می شود . بنابراین، $2 ℓ$ طول محور فرعی بیضی است.

برای تعیین ℓ ، به شکل A2 نگاه می کنیم ، که در آن a و b به ترتیب نقاط تقاطع بیضی با محور اصلی و فرعی آن هستند. اگر به ساختار طناب کشی بیضی فکر کنیم، می توانیم ببینیم که:

د f + د ((ایکس 1 ، y 1) ، الف) + د ((ایکس 2 ، y 2) ، الف) = د f + د ((ایکس 1 ، y 1) ، ب) + د ((ایکس 2 ، y 2) ، ب) ،

از آنجایی که هر دو سمت چپ و راست در این برابری برابر با طول طناب هستند که برای کشیدن بیضی لازم است. ما هم این را می دانیم $d ((x_{1}, y_{1}), a) + d ((x_{2}, y_{2}), a) = 2 L$ ، طول محور اصلی.

علاوه بر این، ما می دانیم که $d ((x_{1}, y_{1}), b) = d ((x_{2}, y_{2}), b) = H,$ از آنجایی که یک مثلث متساوی الاضلاع داریم، اگر طول پاره خطی را که یک نقطه کانونی را با b به هم وصل می کند (یعنی طول هیپوتنوز مثلثی که توسط یک نقطه کانونی، مرکز بیضی و b تشکیل شده است ) بنامیم. بنابراین، دریافت می کنیم $d_{f} + 2 L = d_{f} + 2 H$ یا $L = H$ . قضیه فیثاغورث، اعمال شده بر مثلثی که مرکز بیضی، نقطه کانونی تشکیل شده است. $(x_{1}, y_{1})$ و نقطه b ، سپس می دهد $H^{2} = {(\frac{d_{f}}{2})}^{2} + ℓ^{2}$ . از آنجا که $L = H$ ، ما بدست می آوریم

ℓ = 1 2 4 L 2 - د 2 f ——-\sqrt .

شکل A2. یک بیضی با نقاط کانونی

(x_{1}, y_{1})

(x_{2}, y_{2})

، محور نیمه اصلی L و محور نیمه اصلی ℓ (به رنگ قرمز) و نقاط a و b به ترتیب در محور اصلی و فرعی. طول H پاره خطی که نقطه کانونی را با b متصل می کند با رنگ آبی نشان داده شده است.

در نهایت، اگر $x_{1} \neq x_{2}$ ، شیب خط اتصال را مخفف می کنیم $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ توسط s ، یعنی:

s = y 1 - y 2 ایکس 1 - ایکس 2 .

هدف قضیه زیر و سهم اصلی آن ارائه توصیفی صریح از جعبه مرزی یک بیضی در صفحه با توجه به نقاط کانونی است.

(x_{1}, y_{1})

(x_{2}, y_{2})

از بیضی و محور نیمه اصلی

L > 0

از بیضی از آنجایی که محورهای بیضی لزوماً با محورهای مختصات موازی نیستند، ما همچنین فرمولی را استخراج می کنیم که بیضی را توصیف می کند (از آنجایی که در کتاب های درسی، چنین فرمول هایی معمولاً فقط برای بیضی های “استاندارد” آورده شده است).

قضیه زیر یک نسخه دقیق از قضیه 1 است. بین چهار پیکربندی کانون های بیضی تمایز قائل می شود و به علاوه معادله بیضی را ارائه می دهد.

قضیه 2.

اجازه دهید $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ امتیاز در $R^{2}$ ، و اجازه دهید $L > 0$ یک عدد واقعی باشد معادله بیضی با کانون $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ و محور نیمه اصلی L و جعبه مرزی آن با عبارات زیر به دست می آید:

اگر $(x_{1}, y_{1}) = (x_{2}, y_{2})$ ، سپس:

$(x-_ایکس ج) 2 + (y - y ج) 2 = L 2$

معادله بیضی است و جعبه مرزی با استفاده از $X_{1} = x_{c} - L$ ، $X_{2} = x_{c} + L$ ، $Y_{1} = y_{c} - L$ و $Y_{2} = y_{c} + L$ ;
اگر $x_{1} = x_{2}$ و $y_{1} \neq y_{2}$ ، سپس:

$( x- _ ایکس ج ) 2 ℓ 2 + ( y - y ج ) 2 L 2 = 1$

معادله بیضی است و جعبه مرزی با استفاده از $X_{1} = x_{c} - ℓ$ ، $X_{2} = x_{c} + ℓ$ ، $Y_{1} = y_{c} - L$ و $Y_{2} = y_{c} + L$ ;
اگر $x_{1} \neq x_{2}$ و $y_{1} = y_{2}$ ، سپس:

$( x- _ ایکس ج ) 2 L 2 + ( y - y ج ) 2 ℓ 2 = 1$

معادله بیضی است و جعبه مرزی با استفاده از $X_{1} = x_{c} - L$ ، $X_{2} = x_{c} + L$ ، $Y_{1} = y_{c} - ℓ$ و $Y_{2} = y_{c} + ℓ$ ;
اگر $x_{1} \neq x_{2}$ و $y_{1} \neq y_{2}$ ، سپس:

$( y - y ج - s ( x - ایکس ج ) ) 2 ℓ 2 + ( s ( y - y ج ) + ( x - ایکس ج ) ) 2 L 2 = (1 + س 2)$

معادله بیضی است و جعبه مرزی به صورت زیر بدست می آید:
- $X_{1} = x_{c} - \sqrt{\frac{s^{2} ℓ^{2} + L^{2}}{1 + s^{2}}},$
- $X_{2} = x_{c} + \sqrt{\frac{s^{2} ℓ^{2} + L^{2}}{1 + s^{2}}},$
- $Y_{1} = y_{c} - \sqrt{\frac{s^{2} L^{2} + ℓ^{2}}{1 + s^{2}}}$ و
- $Y_{2} = y_{c} + \sqrt{\frac{s^{2} L^{2} + ℓ^{2}}{1 + s^{2}}} .$

اثبات

اجازه دهید

(x_{1}, y_{1})

(x_{2}, y_{2})

امتیاز در

R^{2}

، و اجازه دهید

L > 0

یک عدد واقعی باشد در هر یک از چهار حالت قضیه، ابتدا می خواهیم معادله بیضی را با کانون ها پیدا کنیم.

(x_{1}, y_{1})

(x_{2}, y_{2})

و نیمه اصلی محور L و سپس برآمدگی آن را روی محور x – و y – تعیین کنید.

سه مورد اول بی اهمیت هستند (هندسه دبیرستان). فقط مورد چهارم نیاز به کمی کار دارد. ما متذکر می شویم که مورد 3 با مورد 4 منطبق است

s = 0

مورد 1.

فرض می کنیم $(x_{1}, y_{1}) = (x_{2}, y_{2})$ . در این حالت بیضی دایره ای با مرکز است $(x_{c}, y_{c}) = (x_{1}, y_{1}) = (x_{2}, y_{2})$ و شعاع L. با معادله به دست می آید:

(x-_ایکس ج) 2 + (y - y ج) 2 = L 2 .

جعبه مرزی این دایره با تعیین می شود $X_{1}, X_{2} = x_{c} \pm L$ و $Y_{1}, Y_{2} = y_{c} \pm L$ .

مورد 2.

فرض می کنیم $x_{1} = x_{2}$ و $y_{1} \neq y_{2}$ . در این حالت یک بیضی داریم که محور اصلی در جهت محور y و محور فرعی در جهت محور x قرار دارد . معادله این بیضی به صورت زیر است:

( x- _ ایکس ج ) 2 ℓ 2 + ( y - y ج ) 2 L 2 = 1 .

جعبه مرزی این دایره با تعیین می شود $X_{1}, X_{2} = x_{c} \pm ℓ$ و $Y_{1}, Y_{2} = y_{c} \pm L$ .

مورد 3.

فرض می کنیم $x_{1} \neq x_{2}$ و $y_{1} = y_{2}$ . در این حالت یک بیضی داریم که در آن محور اصلی در جهت محور x و محور کوتاه در جهت محور y قرار می گیرد . معادله این بیضی به صورت زیر است:

( x- _ ایکس ج ) 2 L 2 + ( y - y ج ) 2 ℓ 2 = 1 .

جعبه مرزی این دایره با تعیین می شود $X_{1}, X_{2} = x_{c} \pm L$ و $Y_{1}, Y_{2} = y_{c} \pm ℓ$ .

مورد 4.

فرض می کنیم

x_{1} \neq x_{2}

y_{1} \neq y_{2}

. بنابراین، برای شیب s ، داریم

s \neq 0

خط ” F ” که کانون ها را به هم وصل می کند $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ معادله دارد $F (x, y) = 0$ ، جایی که:

اف (x ، y) = y - y ج - y 1 - y 2 ایکس 1 - ایکس 2 (x-_ایکس ج) = y - y ج - s (x - ایکس ج) .

خط ” P “، عمود بر F و از طریق $(x_{c}, y_{c})$ ، معادله دارد $P (x, y) = 0$ ، جایی که:

پ (x ، y) = y 1 - y 2 ایکس 1 - ایکس 2 (y - y ج) + (x - ایکس ج) = s (y - y ج) + (x - ایکس ج) .

بیضی با کانون $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ و محور نیمه اصلی L معادله دارد $E (x, y) = 0$ ، با $E (x, y) = \frac{F {(x, y)}^{2}}{A^{2}} + \frac{P {(x, y)}^{2}}{B^{2}} - 1$ یا:

E (x ، y) = ( y - y ج - s ( x - ایکس ج ) ) 2 آ 2 + ( s ( y - y ج ) + ( x - ایکس ج ) ) 2 ب 2 - 1 ،

با $A, B > 0$ .

ما B را با این درخواست می‌یابیم که دو نقطه تلاقی بیضی با محور اصلی در فاصله باشند.

2 L

از یکدیگر. این نقاط تقاطع راه حل های سیستم معادلات هستند

E (x, y) = 0 \land F (x, y) = 0

. از جانب

F (x, y) = 0

، ما گرفتیم

y - y_{c} = s (x - x_{c}) .

اگر از این برابری در

E (x, y) = 0

، ما گرفتیم

{(1 + s^{2})}^{2} {(x - x_{c})}^{2} = B^{2}

یا

x = x_{c} \pm \frac{B}{1 + s^{2}}

برای مختصات x دو نقطه تقاطع. مختصات y مربوطه هستند

y = y_{c} \pm \frac{s B}{1 + s^{2}}

. اگر فاصله بین نقاط را تعیین کنیم

(x_{c} - \frac{B}{1 + s^{2}}, y_{c} - \frac{s B}{1 + s^{2}})

(x_{c} + \frac{B}{1 + s^{2}}, y_{c} + \frac{s B}{1 + s^{2}})

به

2 L

، ما بدست می آوریم

B^{2} = L^{2} (1 + s^{2})

به طور مشابه، A را با الزام به راه حل های سیستم می یابیم $E (x, y) = 0 \land P (x, y) = 0$ هستند $2 ℓ$ جدا از هم. اگر فاصله بین نقاط را تعیین کنیم $(x_{c} - \frac{s A}{1 + s^{2}}, y_{c} + \frac{A}{1 + s^{2}})$ و $(x_{c} + \frac{s A}{1 + s^{2}}, y_{c} - \frac{A}{1 + s^{2}})$ به $2 ℓ$ ، ما بدست می آوریم $A^{2} = ℓ^{2} (1 + s^{2})$ .

{آ 2 ب 2 = = ℓ 2 (1 + س 2) L 2 (1 + س 2) ، و

بنابراین، معادله بیضی با کانون $(x_{1}, y_{1})$ و $(x_{2}, y_{2})$ و محور نیمه اصلی L با معادله به دست می آید $E (x, y) = 0$ ، جایی که:

E (x ، y) = ( y - y ج - s ( x - ایکس ج ) ) 2 ℓ 2 + ( s ( y - y ج ) + ( x - ایکس ج ) ) 2 L 2 - (1 + س 2) .

برای تعیین جعبه مرزی این بیضی، بردار را در نظر می گیریم:

(\partial E \partial ایکس ، \partial E \partial y) ،

که برای یک امتیاز $(x_{0}, y_{0})$ روی بیضی (یعنی برای آن $E (x_{0}, y_{0}) = 0$ ) جهت عمود بر بیضی را هنگامی که در ارزیابی می شود می دهد $(x_{0}, y_{0})$ .

وقتی تنظیم کردیم $\frac{\partial E}{\partial x} = 0$ ، این عمود در جهت محور y است . معادله $\frac{\partial E}{\partial x} = 0$ است:

s (y - y ج) (ℓ 2 - L 2) + (x - ایکس ج) (س 2 L 2 + ℓ 2) = 0

یا:

x - ایکس ج = س ( L 2 - ℓ 2 ) س 2 L 2 + ℓ 2 (y - y ج) ،

که خطی را مشخص می کند که بیضی را در دو نقطه قطع می کند. وقتی جایگزین می کنیم $x - x_{c}$ از معادله این خط در معادله بیضی، مرزهای پایین و بالایی جعبه مرزی را به دست می آوریم:

Y 1 = y ج - س 2 L 2 + ℓ 2 1 + س 2 ——-\sqrt ،

و:

Y 2 = y ج + س 2 L 2 + ℓ 2 1 + س 2 ——-\sqrt .

وقتی تنظیم کردیم $\frac{\partial E}{\partial y} = 0$ ، عمود بر بیضی در جهت محور x است . معادله $\frac{\partial E}{\partial y} = 0$ است:

(y - y ج) (L 2 + س 2 ℓ 2) + (x - ایکس ج) s (ℓ 2 - L 2) = 0

یا:

y - y ج = س ( L 2 - ℓ 2 ) س 2 ℓ 2 + L 2 (x-_ایکس ج) ،

که خطی را مشخص می کند که بیضی را در دو نقطه قطع می کند. وقتی جایگزین می کنیم $y - y_{c}$ از معادله این خط در معادله بیضی، کران چپ و راست کادر مرزی را بدست می آوریم:

ایکس 1 = ایکس ج - س 2 ℓ 2 + L 2 1 + س 2 ——-\sqrt ،

و:

ایکس 2 = ایکس ج + س 2 ℓ 2 + L 2 1 + س 2 ——-\sqrt .

این اثبات را کامل می کند.

منابع

جیانوتی، اف. Pedreschi, D. Mobility, Data Mining and Privacy-Geographic Knowledge Discovery ; Springer: برلین، آلمان، 2008. [ Google Scholar ]
سفید، CE; برنشتاین، دی. Kornhauser، AL برخی از الگوریتم های تطبیق نقشه برای دستیاران ناوبری شخصی. ترانسپ Res. قسمت C Emerg. تکنولوژی 2000 ، 8 ، 91-108. [ Google Scholar ] [ CrossRef ]
گوتینگ، RH; Schneider, M. Moving Object Databases ; مورگان کافمن: سانفرانسیسکو، کالیفرنیا، ایالات متحده آمریکا، 2005. [ Google Scholar ]
ین، JY یافتن طول تمام کوتاه ترین مسیرها در شبکه های کامل با فاصله غیرمنفی گره N با استفاده از $\frac{1}{2}$ N ³ اضافات و N ³ مقایسه. J. ACM 1972 , 19 , 423-424. [ Google Scholar ] [ CrossRef ]
هاشمی، م. کریمی، HA مروری انتقادی از الگوریتم های تطبیق نقشه بلادرنگ: مسائل جاری و جهت گیری های آینده. محاسبه کنید. محیط زیست سیستم شهری 2014 ، 48 ، 153-165. [ Google Scholar ] [ CrossRef ]
برنشتاین، دی. Kornhauser، AL مقدمه ای بر تطبیق نقشه برای دستیارهای ناوبری شخصی ؛ گزارش فنی؛ هیئت تحقیقات حمل و نقل: واشنگتن، دی سی، ایالات متحده آمریکا، 1998. [ Google Scholar ]
Eddy, SR مدل مخفی مارکوف چیست؟ نات. بیوتکنول. 2004 ، 22 ، 1315-1316. [ Google Scholar ] [ CrossRef ] [ PubMed ]
نیوزون، پی. Krumm, J. Hidden Markov نقشه مطابق با نویز و پراکندگی. در مجموعه مقالات هفدهمین سمپوزیوم بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، نیویورک، نیویورک، ایالات متحده آمریکا، 4 تا 6 نوامبر 2009.
کروم، جی. لچنر، جی. Horvitz، E. تطبیق نقشه با محدودیت های زمان سفر. در مجموعه مقالات انجمن مهندسان خودرو (SAE) کنگره جهانی 2007، دیترویت، MI، ایالات متحده آمریکا، 3-6 آوریل 2007.
Greenfeld، JS تطبیق مشاهدات GPS با مکان‌های روی نقشه دیجیتال. در مجموعه مقالات هشتاد و یکمین نشست سالانه هیئت تحقیقات حمل و نقل، واشنگتن دی سی، ایالات متحده آمریکا، 13 تا 17 ژانویه 2002.
برکاتسولاس، اس. Pfoser، D.; سالاس، آر. Wenk, C. در مورد داده های ردیابی وسیله نقلیه مطابق با نقشه. در مجموعه مقالات سی و یکمین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تورنتو، ON، کانادا، 31 اوت تا 3 سپتامبر 2005.
ونک، سی. سالاس، آر. Pfoser، D. پرداختن به نیاز به سرعت تطبیق نقشه: بومی سازی الگوریتم های تطبیق منحنی جهانی. در مجموعه مقالات هجدهمین کنفرانس بین المللی مدیریت پایگاه داده های علمی و آماری، وین، اتریش، 3 تا 5 ژوئیه 2006.
کالمن، RE یک رویکرد جدید برای فیلتر کردن خطی و مشکلات پیش‌بینی. ترانس. ASME J. مهندس پایه. 1960 ، 82 ، 35-45. [ Google Scholar ] [ CrossRef ]
قدوس، م. ژائو، ال. Ochieng، WY; Noland, RB یک الگوریتم فیلتر کالمن توسعه یافته برای یکپارچه سازی GPS و داده های سیستم محاسبه مرده کم هزینه برای عملکرد خودرو و نظارت بر انتشار گازهای گلخانه ای. جی. ناویگ. 2003 ، 56 ، 257-275. [ Google Scholar ]
لی، ال. قدوس، م. ژائو، ال. الگوریتم نظارت بر یکپارچگی با دقت بالا برای تطبیق نقشه. ترانسپ Res. قسمت C Emerg. تکنولوژی 2013 ، 36 ، 13-26. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
قدوس، م. Ochieng، WY; نولاند، تطبیق نقشه RB در شبکه های پیچیده جاده های شهری. براز جیم کارتوگر. Revista Brasil. کارتوگر. 2003 ، 55 ، 1-18. [ Google Scholar ]
Zadeh, LA Fuzzy sets. Inf. کنترل 1965 ، 8 ، 338-353. [ Google Scholar ] [ CrossRef ]
Zhao, Y. سیستم های مکان یابی و ناوبری خودرو: سیستم های حمل و نقل هوشمند . سمینارهای Navtech و تامین GPS: اسکندریه، ویرجینیا، ایالات متحده آمریکا، 1997. [ Google Scholar ]
سید، س. Cannon، ME الگوریتم تطبیق نقشه مبتنی بر منطق فازی برای سیستم ناوبری خودرو در دره های شهری. در مجموعه مقالات نشست فنی ملی 2004 موسسه ناوبری، مونتری، کالیفرنیا، ایالات متحده آمریکا، 26-28 ژانویه 2004.
Quddus، MA الگوریتم های تطبیق نقشه با یکپارچگی بالا برای برنامه های کاربردی تله ماتیک حمل و نقل پیشرفته. دکتری پایان نامه، امپریال کالج، لندن، انگلستان، 2006. [ Google Scholar ]
لو، ی. ژانگ، سی. ژنگ، ی. Xie، X. وانگ، دبلیو. Huang, Y. تطبیق نقشه برای مسیرهای GPS با نرخ نمونه برداری پایین. در مجموعه مقالات هفدهمین سمپوزیوم بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، WA، ایالات متحده آمریکا، 4-6 نوامبر 2009.
لی، ی. هوانگ، Q. کربر، م. ژانگ، ال. Guibas، L. تطبیق نقشه مشترک در مقیاس بزرگ از ردیابی GPS. در مجموعه مقالات بیست و یکمین کنفرانس بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، نیویورک، نیویورک، ایالات متحده آمریکا، 5 تا 8 نوامبر 2013.
تانگ، جی. آهنگ، ی. میلر، اچ جی; ژو، X. تخمین محتمل ترین مسیرهای فضا-زمان، زمان اقامت و عدم قطعیت های مسیر از داده های مسیر وسیله نقلیه: یک روش جغرافیایی زمانی. ترانسپ Res. قسمت C Emerg. تکنولوژی 2016 ، 66 ، 176-194. [ Google Scholar ] [ CrossRef ]
چن، توسط; یوان، اچ. لی، کیو. لام، WHK; شاو، اس. Yan, K. الگوریتم تطبیق نقشه برای داده‌های ماشین شناور با فرکانس پایین در مقیاس بزرگ. بین المللی جی. جئوگر. Inf. علمی 2014 ، 28 ، 22-38. [ Google Scholar ] [ CrossRef ]
وانگ، دبلیو. جین، جی. ران، بی. Guo, X. نظارت بر ترافیک شبکه آزادراه در مقیاس بزرگ: یک الگوریتم تطبیق نقشه بر اساس داده های کاوشگر GPS با فرکانس پایین ثبت. جی. اینتل. ترانسپ سیستم 2011 ، 15 ، 63-74. [ Google Scholar ] [ CrossRef ]
میوا، تی. کیوچی، دی. یاماموتو، تی. موریکاوا، تی. توسعه الگوریتم تطبیق نقشه برای داده های پروب فرکانس پایین. ترانسپ Res. قسمت C Emerg. تکنولوژی 2016 ، 22 ، 132-145. [ Google Scholar ] [ CrossRef ]
رحمانی، م. کوتسوپولوس، اچ. استنتاج مسیر از داده‌های خودروی شناور پراکنده برای شبکه‌های شهری. ترانسپ Res. قسمت C Emerg. تکنولوژی 2013 ، 30 ، 41-54. [ Google Scholar ] [ CrossRef ]
هانتر، تی. آببل، پ. باین، AM فیلتر استنتاج مسیر: تطبیق نقشه کم تأخیر مبتنی بر مدل داده‌های خودروی کاوشگر. IEEE Trans. هوشمند ترانسپ سیستم 2014 ، 15 ، 507-529. [ Google Scholar ] [ CrossRef ]
زنگ، ز. ژانگ، تی. لی، کیو. وو، زی. زو، اچ. Gao, C. ویژگی انحنای تطبیق نقشه محدود برای داده‌های خودروی کاوشگر فرکانس پایین. بین المللی جی. جئوگر. Inf. علمی 2016 ، 30 ، 660-690. [ Google Scholar ] [ CrossRef ]
Pfoser، D.; جنسن، CS ثبت عدم قطعیت بازنمایی‌های شی متحرک. در یادداشت های سخنرانی در علوم کامپیوتر ; Güting, RH, Papadias, D., Lochovsky, FH, Eds. Springer: برلین، آلمان، 1999; صص 111-132. [ Google Scholar ]
Egenhofer، MJ تقریب خطوط حیاتی جغرافیایی. در SpadaGIS، کارگاه آموزشی داده های مکانی و سیستم های اطلاعات جغرافیایی ; Bertino, E., Floriani, LD, Eds. دانشگاه جنوا: جنوا، ایتالیا، 2003. [ Google Scholar ]
هورنسبی، ک. Egenhofer، MJ مدل سازی اجسام متحرک بر روی دانه بندی های متعدد. ان ریاضی. آرتیف. هوشمند 2002 ، 36 ، 177-194. [ Google Scholar ] [ CrossRef ]
Wolfson, O. مدیریت اطلاعات اشیاء متحرک: چالش پایگاه داده. در یادداشت های سخنرانی در علوم کامپیوتر ; Halevy, AY, Gal, A., Eds. Springer: برلین، آلمان، 2002; صص 75-89. [ Google Scholar ]
Hägerstrand، T. در مورد افراد در علم منطقه چطور؟ ثبت اوراق علمی دانشیار 1970 ، 24 ، 7-21. [ Google Scholar ] [ CrossRef ]
میلر، HJ نظریه اندازه گیری برای جغرافیای زمانی. Geogr.l مقعدی. 2005 ، 37 ، 17-45. [ Google Scholar ] [ CrossRef ]
Othman, W. مدیریت عدم قطعیت در پایگاه های داده مسیر. دکتری پایان نامه، دانشگاه هاسلت، هاسلت، بلژیک، 2009. [ Google Scholar ]
هارت، PE; نیلسون، نیوجرسی؛ رافائل، بی. مبنایی رسمی برای تعیین اکتشافی مسیرهای حداقل هزینه. IEEE Trans. سیستم علمی سایبرن. 1968 ، 4 ، 100-107. [ Google Scholar ] [ CrossRef ]
Dijkstra، EW در مورد دو مشکل در ارتباط با نمودارها. عدد. ریاضی. 1959 ، 1 ، 269-271. [ Google Scholar ] [ CrossRef ]
غیس، ک. کویجپرز، بی. مولانز، بی. عثمان، دبلیو. ونگوئیدسنهوون، دی. Vaisman، تطبیق نقشه AA و عدم قطعیت: یک الگوریتم و آزمایش های دنیای واقعی. در مجموعه مقالات هفدهمین سمپوزیوم بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، دی سی، ایالات متحده آمریکا، 4 تا 6 نوامبر 2009.

شکل 1. سمت چپ : نمونه ای از نرخ نمونه برداری بالا. دایره های اطراف نقاط GPS نشان دهنده ناحیه اطمینان هستند. یک مسیر از نقطه شروع A تا پایان نقطه B وجود دارد، به طوری که حداقل یک نقطه در هر بخش می افتد. راست : نمونه ای از نرخ نمونه گیری پایین. هیچ مسیری از نقطه A تا B وجود ندارد.

شکل 2. نمونه ای از منشور فضا-زمان به عنوان محل تلاقی یک مخروط رو به بالا و پایین.

شکل 3. نمونه ای از جعبه مرزی برای دو نقطه نمونه متوالی با فاصله زمانی 35 ثانیه (در سمت چپ ) و برای دو نقطه متوالی با فاصله زمانی یک ثانیه (در سمت راست ).

شکل 4. یک شبکه جاده برای مثال 1.

شکل 5. یک مشکل با رویکردهای کوتاه ترین مسیر.

شکل 6. نمادها

A, . . ., M

نقاط نمونه و نمادها را نشان می دهد

1, . . ., 18

شناسه بخش های جاده هستند.

شکل 7. نمونه ای از شروع مسیر مبهم.

شکل 8. میانگین نتایج الگوریتم های تطبیق نقشه (MM) روی 20 نمونه مسیر از مجموعه داده پلیس گنت.

شکل 9. میانگین نتایج الگوریتم‌های MM بر روی ده نمونه مسیری تولید شده توسط کامپیوتر بدون خطای اندازه‌گیری ( سمت چپ ) و با ( سمت راست ).

شکل 10. میانگین نتایج الگوریتم های MM روی ده نمونه مسیر تولید شده توسط کامپیوتر با خطاهای اندازه گیری و نقاط پرت ( سمت چپ ) و با خطاها و شکاف های اندازه گیری ( سمت راست ).

شکل 11. میانگین نتایج الگوریتم های MM در ده مسیر تولید شده توسط کامپیوتر شبیه سازی رانندگی در بزرگراه با خطاهای GPS ( سمت چپ ) و در ده مسیر طولانی تولید شده توسط کامپیوتر با خطاهای اندازه گیری ( سمت راست ).

شکل 12. میانگین نتایج الگوریتم های MM در ده مسیر تولید شده توسط کامپیوتر با نرخ نمونه برداری پایین ( سمت چپ ) و بدون خطای اندازه گیری و خطای اندازه گیری ( سمت راست ).

شکل 13. میانگین نتایج از شکل 8 ، شکل 9 ، شکل 10 ، شکل 11 و شکل 12 .

شکل 14. میانگین زمان اجرا در ثانیه از نتایج داده های نشان داده شده در شکل 8 ، شکل 9 ، شکل 10 ، شکل 11 و شکل 12 ، که در آن، برای دید، ما خط نارنجی را در 80 ثانیه برش می دهیم.

جدول 1. نمونه ای از الگوریتم تخصیص وزن ها.

جدول 2. میانگین زمان اجرا بر حسب ثانیه از الگوریتم های MM برای مجموعه داده پلیس گنت.

© 2016 توسط نویسندگان؛ دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution (CC-BY) (http://creativecommons.org/licenses/by/4.0/) توزیع شده است.

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

سازمان

2. مروری بر رویکردهای موجود برای تطبیق نقشه

2.1. طبقه بندی الگوریتم های تطبیق نقشه

2.2. مروری کوتاه بر الگوریتم های تطبیق نقشه

2.2.1. الگوریتم های هندسی

2.2.2. الگوریتم های توپولوژیکی

2.2.3. الگوریتم های احتمالی

2.3. الگوریتم‌هایی برای داده‌ها با نرخ نمونه‌گیری پایین

3. الگوریتم تطبیق نقشه مبتنی بر عدم قطعیت

3.1. مقدمه ای بر منشورهای فضا-زمان

3.2. استفاده از منشورهای فضا-زمان برای تطبیق نقشه

3.2.1. محاسبات پروجکشن منشور فضا-زمان و جعبه مرزی آن

3.2.2. استفاده از جعبه‌های مرزی پروجکشن منشورهای فضا-زمان در تطبیق نقشه

3.2.3. الگوریتمی برای مسیریابی k -کوتاهترین مسیر

3.2.4. شرح الگوریتم تطبیق نقشه منشورهای فضا-زمان

4. ارزیابی بهبود یافته الگوریتم های تطبیق نقشه

4.1. منابع و ویژگی های داده

4.2. روش‌هایی برای اندازه‌گیری کیفیت الگوریتم تطبیق نقشه

4.3. مشکلات در اندازه گیری دقت

4.4. اندازه گیری دقت جدید: CL-Accuracy

5. مقایسه تجربی الگوریتم های تطبیق نقشه

5.1. آزمایش بر روی داده های برچسب انسانی

5.2. آزمایشات روی داده های تولید شده توسط کامپیوتر

5.2.1. نرخ نمونه برداری بالا

نمونه های مسیر شبیه سازی شده بدون خطای اندازه گیری

نمونه های مسیر شبیه سازی شده با خطاهای اندازه گیری

نمونه های مسیر شبیه سازی شده با خطاهای اندازه گیری و نقاط پرت

نمونه های مسیر شبیه سازی شده با خطاها و شکاف های اندازه گیری

نمونه های مسیر شبیه سازی شده در بزرگراه با خطاهای GPS

نمونه های مسیر شبیه سازی شده در مسافت طولانی با خطاهای اندازه گیری

5.2.2. نرخ نمونه برداری پایین

نمونه های مسیر شبیه سازی شده بدون خطای اندازه گیری

نمونه های مسیر شبیه سازی شده با خطاهای اندازه گیری

5.3. بحث

6. نتیجه گیری و مسائل باز

ضمیمه الف. محاسبات طرح ریزی یک منشور فضا-زمان و جعبه مرزی آن

منابع

قبلیالگوریتم خوشه‌بندی سری‌های زمانی مبتنی بر چگالی تطبیقی: مطالعه موردی الگوهای بارش

بعدیشناخت الگوهای حرکتی تکراری-مورد تحلیل فوتبال

بدون نظر

دیدگاهتان را بنویسید لغو پاسخ