אלגוריתם A* מודע לכיוון ומתאים עצמו עם היוריסטיקה PPO לתכנון מסלול רחפנים בעיר חכמה

נתיבים חכמים יותר לרחפני העיר

דמיינו צי של רחפני משלוחים קטנים המתפתלים בין גורדי שחקים, מביאים תרופות, חבילות או אספקה חירום ברחבי עיר תוססת. כדי לטוס בבטחה ובמהירות, כל רחפן חייב להחליט כל הזמן לאן להמשיך. המאמר הזה מציג שיטה חדשה לרחפנים למצוא נתיבים טובים יותר במרחבים עירוניים תלת־ממדיים צפופים, מה שהופך את המסלולים שלהם לקצרים, חלקים ואמינים יותר מאשר בשיטות המסורתיות.

מדוע מציאת מסלול טוב כל כך קשה

עבור רחפן, בחירת מסלול היא הרבה יותר מאשר שרטוט קו ישר מנקודה A לנקודה B. עליו להתחמק מבניינים, עצים ואזורים אסורים לטיסה תוך שמירה על מגבלות סיבוב וגובה. שיטות קלאסיות לתכנון מסלול, כדוגמת אלגוריתם A* המוכר, עובדות היטב על מפות פשוטות אך מתקשות בהגדרות עירוניות תלת־ממדיות מציאותיות. לעתים הן בודקות יותר מדי צעדים אפשריים, מבזבזות משאבי חישוב ועלולות לייצר מסלולים זיגזגיים שארוכים מהנדרש או אפילו נכשלות כשהסביבה צפופה מאוד. ככל שהערים החכמות הופכות למורכבות יותר, חולשות אלו הופכות לצוואר בקבוק משמעותי בניהול תעבורת אוויר בטוחה ויעילה.

שדרוג מודע־כיוון לכלי קלאסי

המחברים בונים על אלגוריתם A* ומציעים גרסה משופרת הנקראת DASA* (A* מודע־כיוון ומתאים־עצמו). במקום להסתכל בעוינות בכל הכיוונים סביב הרחפן, DASA* שמה לב לאן נמצא היעד. היא ממיינת מיקומי מועמדים בקרבת מקום לשלוש שכבות: אלה שנמצאים בעיקר מול הרחפן בכיוון היעד, אלה בצדדים וקבוצה קטנה מאחור שיכולה לסייע ביציאה ממבואות סתומים. גלאי תקיעות פשוט עוקב אחרי סימנים שהחיפוש "נתקע" ואז מרחיב אוטומטית את החיפוש ממחוג קדמי צר לשכונה רחבה יותר לפי הצורך. הרחבה זהירה וממוקדת־מטרה זו מפחיתה חיפושים מיותרים בזמן שעדיין מבטיחה שמסלול תקף יימצא אם קיים.

הסתגלות לחללים צפופים ופתוחים

מאפיין מרכזי נוסף של DASA* הוא שהיא משנה את צעדיה בהתאם לסביבה. כשהרחפן רחוק מהמכשולים, האלגוריתם עושה צעדים גדולים יותר וכך מכסה במהירות שטחים פתוחים. ככל שמתקרב לבניינים או לסכנות אחרות, הוא עובר לצעדים קטנים יותר, מה שמאפשר תמרון מדויק במרווחים צרים. "רמת הזום" המשתנה הזו מאפשרת לתכנן במהירות במקום בטוח ולהאט רק כשהדיוק חשוב. לאחר שמסלול גולמי נמצא, שלב כוונון ייעודי מסיר נקודות דרך מיותרות ומיישר עקומה חלקה דרך נקודות המפתח שנותרו. התוצאה היא מסלול שמונע התנגשות ומזכיר יותר נתיב טיסה טבעי שבחר טייס מיומן, עם פחות סיבובים פתאומיים.

ללמד את האלגוריתם להסתכל קדימה

A* המסורתי נשען על נוסחאות מרחק פשוטות כדי לאמוד כמה רחוקה כל נקודה מהיעד. DASA* מחליפה את ההערכה הזו במדריך שנלמד מבוסס Proximal Policy Optimization (PPO), טכניקת חיזוק מודרנית. בסביבת אימון, סוכן וירטואלי מתרגל שוב ושוב לנוע לעבר מטרה במרחב תלת־ממדי בעודו חשה מרחקים, הבדלי גובה ומידע כיווני. רשת עצבית לומדת בהדרגה עד כמה כל מצב מבטיח ולאחר האימון משמשת כ"מודול אינטואיציה" שניתן להציב בתוך DASA*. היוריסטיקה הנלמדת הזו מנווטת את החיפוש ישירות יותר לעבר פתרונות טובים, במיוחד בפריסות מורכבות שבהן מרחק בקו ישר מטעה.

כמה טוב זה עובד בערים מדומות

החוקרים בדקו את DASA* במספר תרחישים עירוניים תלת־ממדיים מדומים מלאים בבנייני קופסה ומכשולים גליליים המדמים מבנים עירוניים אמיתיים. הם השוו אותה ל‑A* הקלאסי ולכמה חלופות פופולריות, כולל גרסאות משופרות של Rapidly Exploring Random Trees, חבורות חלקיקים, אבולוציה דיפרנציאלית ועוד וריאנט של A* בשם Theta*. לאורך מקרים רבים, DASA* מצאה בעקביות מסלולים קצרים יותר, הרחיבה הרבה פחות נקודות מועמדות ופעלה הרבה יותר מהר—לעתים 10 עד 50 פעמים מהיר יותר מ‑A* הסטנדרטי. היא גם שמרה על שיעור הצלחה מושלם או כמעט מושלם אפילו בסביבות צפופות ומבוכיות, בעוד שאחרות נכשלו לעיתים תכופות יותר או ייצרו סטיות ארוכות ומעגליות.

מה זה אומר לחיי היומיום

במילים פשוטות, DASA* נותנת לרובוטים מעופפים תחושת כיוון ושיפוט טובה יותר. על ידי התמקדות בכיוונים מבטיחים, התאמת רמת הפירוט לסביבה המקומית, שימוש בתחושה נלמדת לגבי קרבה להצלחה והחלקת המסלול הסופי, היא הופכת נתוני מפה גולמיים לנתיבי טיסה יעילים, חלקים ומעשיים. אם יאומץ במערכות אמיתיות, גישה כזו עשויה לסייע לערים חכמות עתידיות לנהל משלוחים בחלל האוויר, בדיקות ומענה חירום בצורה בטוחה ואמינה יותר, גם כאשר השמיים נהיים צפופים והסביבות מורכבות יותר.

ציטוט: Zhang, X., Tan, L. & Chai, J. Direction aware and self-adaptive A* algorithm with PPO heuristic for UAV path planning of smart city. Sci Rep 16, 6174 (2026). https://doi.org/10.1038/s41598-026-36066-4

מילות מפתח: תכנון מסלולים לרחפנים, רחפנים בעיר חכמה, אלגוריתם A*, ניווט אוטונומי, תכנון תנועה רובוטית