Conflict-based Search with Agent-Relative Constraints for the Multi-Agent Problem | Khalid Ajran
Conflict-based Search with Agent-relative Constraints for the Multi-agent Pathfinding Problem
Khalid Ajran, RISS 2023 Cohort
Carnegie Mellon University
Robotics Institute Summer Scholars: https://riss.ri.cmu.edu/
In the multi-agent pathfinding problem (MAPF), we are given a set of agents with respective start and goal locations in a shared environment, and the task is to find a collision-free set of trajectories for the agents with minimal cost. A popular, optimal algorithm for the MAPF problem is Conflict Based Search (CBS). Roughly, CBS divides the search process into two levels: A high level search for a set of constraints to impose on the agents individually, and a low level search in the environment to find paths for the agents satisfying the constraints imposed by the high level. The constraints used in the high level are space-time constraints, preventing agents from going to a certain location at a given time locations to avoid collisions, but can result in some constraints becoming irrelevant as agents continually replan their paths. In this paper, we propose some alternative constraint types which dynamically change as agents replan, requiring fewer constraints in total. We conduct experiments that reveal that our variants perform similarly or slightly better in general scenarios, with more dramatic improvements in small, complicated maps.
*****
The Robotics Institute Summer Scholars (RISS) Program at Carnegie Mellon University's School of Computer Science
Carnegie Mellon University’s Robotics Institute is committed to opening doors and creating opportunities for future leaders in robotics. Carnegie Mellon University is home to the top-ranked School of Computer Science, the world’s first university robotics department, the world’s first Ph.D. in robotics, and the largest university-affiliated robotics research group. Launched in 2006, CMU’s Robotics Institute Summer Scholars (RISS) program (http://riss.ri.cmu.edu/)comprises a ten-week summer undergraduate research program that immerses a diverse cohort of scholars in cutting-edge robotics and extensive post-program mentoring. The program provides opportunities for students from across the country and the world to conduct research with leaders in the field. The program aspires to foster a diverse and inclusive working and learning environment where all students enjoy the educational benefits of diversity and are actively welcomed, included, and supported by the community. The quality and breadth of research, high level of institute and university engagement, and powerful professional development programming, graduate school application counseling, and alumni network create transformative experiences and remarkable post-program trajectories.
RESEARCH RESULTS:
Explore our research projects and results at:
Videos & Posters at https://riss.ri.cmu.edu/research_show...
Working Papers Journal at https://riss.ri.cmu.edu/research_show...
SCHOLARSHIPS: The RISS program partners and community provide extensive scholarships for students selected to participate. Scholarships are available to students from across the US and the world.
APPLY: Starting November 1st at https://riss.ri.cmu.edu/
SCHOLAR EXPERIENCE: Scholars contribute, communicate, & connect.
Contribute: Scholars contribute to robotics research projects through a guided research experience with multiple layers of mentorship.
Communicate: Scholars learn how to effectively communicate research ideas to various audiences (e.g., sponsors, academic audience, novice audiences) and in various formats (e.g., elevator pitches, short talks, research papers, and poster presentations).
Connect: Scholars forge long-lasting connections to Carnegie Mellon University researchers and partners.
PROFESSIONAL SKILLS DEVELOPMENT: The RISS communications workshop series includes workshops and one-on-one tutoring on writing research & technical papers, designing graphics, and presenting posters. Their impressive results are a reflection of the deep partnerships and commitment of partners’ teaching contributions.
Robotics Workshops & Talks: The technical professional development series exposes scholars to a wide range of robotics applications and projects through weekly robotics talks, visits to labs, and hands-on workshops.
COMMUNITY: We foster the creation of a supportive learning community through intentional messaging, welcoming events, and effective programming. Onboarding includes virtual orientation sessions and office hours, a cohort Slack group, on-site orientation, and weekly office hours. Programming is structured to engage students in deep interactions – from workshop teams to peer reviews for papers and posters. Projects require students to go beyond their current skill set and to learn from others. Over 75 individuals participate as mentors, presenters, or programming partners annually.