تشخیص خودکار مکان چراغ قرمز‌ها

نقشه و مسیریاب نشان چگونه مکان چراغ قرمز‌ها را تشخیص می‌دهد؟

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

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

شرح مسئله

ما برای بهبود پیش‌بینی زمان سفر، مسیریابی‌ دقیق‌تر و بهبود کیفیت تجربه‌ کاربری نیاز داشتیم برای تشخیص هوشمند مکان چراغ‌ قرمز‌ها، الگوریتمی رو با پارامتر‌های زیر ارائه بدیم:

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

جنس داده‌ها و محدودیت‌ها

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

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

توضیح درباره‌ نتورک خیابان‌ها

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

مثلا در شکل بالا راس‌های گراف پررنگ‌تر مشخص شدن و یال‌های گراف، همون خیابان‌ها و کوچه‌ها هستن که با رنگ خاکستری نشون داده شدن.

پیدا کردن پترن‌های مختلف در نتورک خیابان‌ها

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

به‌طور کلی پترن‌هایی که به دنبالشون گشتیم این‌ها بودن:

اما چطور باید این پترن‌ها رو در نتورکی که بیشتر از چند ده میلیون راس و یال داره پیدا می‌کردیم؟

مسئله‌ subgraph monomorphism

یک گراف رو با مجموعه‌ یال‌ها و راس‌های اون مدل‌سازی می‌کنند. گراف G با مجموعه‌ یال‌های E و راس‌های V رو در نظر بگیرید. همچنین یک گراف کوچک‌تر H که یال‌هاش E' و راس‌هاش V' هست رو تصور کنید. تعریف ریاضی یک‌ریختی یا Isomorphism بین گراف G و گراف H، یک تابع از راس‌های H به راس‌های G هست که یال‌های گراف رو حفظ کنه.

مثلا به شکل زیر توجه کنین، تابع f تعریف شده در شکل زیر یک Isomorphism بین گراف G و H هست. همون‌طور که می‌بینین این تابع هر یک از رئوس گراف G رو به یکی از نقاط H تناظر داده و در عین حال بعد از تناظر تمام یال‌های گراف H حفظ شدن. یعنی مثلا یال (1, 2) در گراف H وجود داره اگر و فقط اگر دو راس مانند a, h در گراف G وجود داشته باشه که اولا f(a) = 1 و f(h) = 2 و ثانیا یال (a, h) هم در گراف G حضور داشته باشه.

مسئله‌ای که ما به دنبال حل کردن اون هستیم اینه که در هر زیرگراف از گراف نتورک دنبال چنین Isomorphism بین اون زیرگراف و پترن‌هامون باشیم؛ ولی چیزی که ما می‌خوایم اینه که یال‌های گراف در تابع یک‌ریختی حفظ بشه و فقط لازمه که یال‌های پترنی که دنبال اون هستیم، در زیر گراف القایی که توسط تابع یک‌ریختی ایجاد می‌شه وجود داشته باشه. به این تابع که رئوس دو گراف رو به هم منتقل می‌کنه اما لزوما تمام یال‌های گراف اصلی را نگه نمی‌داره Monomorphism گفته می‌شه. به شکل زیر توجه کنین:

مثلا در این شکل تابع f نوشته‌شده یک Isomorphism بر روی زیرگراف G_{1,2,3,4,5,6} نیست، چرا که یال (1,2) رو حفظ نکرده؛ اما یک Monomorphism هست چون هر یالی که در گراف P وجود داره، در زیرگراف G_{1,2,3,4,5,6} هم وجود داره. حل این مسئله در حالت کلی تحت عنوان Subgraph Monorphism شناخته می‌شه و در دسته‌ مسائل NP قرار می‌گیره، یعنی الگوریتم کارایی برای حل اون وجود نداره. در عین حال روش‌هایی وجود داره که با تقریب‌ قابل اتکایی این مسئله‌ رو به‌صورت کارا حل می‌کنه. یکی از این روش‌ها الگوریتم VF2 هست که یکی از شناخته‌‌شده‌ترین روش برای حل این مسئله‌ست.

نتیجه‌گیری

با این روش به‌خوبی تونستیم پترن‌های مختلف نتورکی رو در گراف خیابان‌ها پیدا کنیم. مثلا برای یکی از پترن‌های مربوط به نشون دادن چهارراه‌های دو طرفه، زیرگراف زیر رو در نظر گرفتیم:

با در نظر گرفتن این زیرگراف و جست‌وجو کردن اون در گراف اصلی خیابان‌ها، خروجی زیر در بخشی از شهر تهران به این شکل در اومد:

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