נושא הפרוייקט
מספר פרוייקט
מחלקה
שמות סטודנטים
אימייל
שמות מנחים
מציאת מסלולים במערכת מרובת סוכנים תחת אי וודאות של מכשולים
Online Multi Agent Path Finding Under Obstacle Uncertainty
תקציר בעיברית
בבעית מציאת מסלולים במערכת מרובה סוכנים (MAPF), מספר סוכנים צריכים לעבור ממיקומם הנוכחי אל עבר עמדות היעד שלהם מבלי להתנגש זה בזה. עבודות קודמת בתחום הניחו ידע מלא על הסביבה. במחקר זה, אנו משמיטים הנחה זו, כלומר המתכנן לא יודע מראש האם עמדות מסוימות נגישות. כדי לאשש אם עמדה כזו ניתנת למעבר, על סוכן להתקרב אליה ולהתאים התנהגותו. בעבודה זו אנו מתמקדים בפתרון בעיית MAPF מסוג זה, למקרים בהם התכנון מרוכז אך אינו ניתן ליישום במהלך הביצוע. במסגרת זו, ניתן לגבש פתרון כעץ תכנית לכל סוכן, המסתעף על התצפיות. אנו מציעים אלגוריתמים למציאת עצי תוכניות כאלה לשני אופני ביצוע: ריכוזי, שבו הסוכנים חולקים מידע בנוגע למכשולים שנצפו במהלך הביצוע, מבוזר, שבו תקשורת כזו אינה מותרת.
תקציר באנגלית
In multi-agent path finding (MAPF), several agents must move from their current positions to their target positions without colliding. Prior work on MAPF commonly assumed perfect knowledge of the environment. We consider a MAPF setting where this is not the case, and the planner does not know a-priori whether some positions are blocked or not. To sense whether such a position is traversable, an agent must move close to it and adapt its behavior accordingly. In this work we focus on solving this type of MAPF problem, for cases where planning is centralized but cannot be done during execution. In this setting, a solution can be formulated as a plan tree for each agent, branching on the observations. We propose algorithms for finding such plans trees for two modes of executions: centralized, where the agents share information concerning observed obstacles during execution, a decentralized, where such communication is not allowed.