Vi studerar praktiska metoder för att lösa problemet med token swapping (TSWAP) optimalt i detta dokument. I TSWAP får vi en oriktad graf med färgade hörn. En färgad token placeras i varje vertex. Ett par polletter kan bytas mellan angränsande hörn. Målet är att utföra en sekvens av byten så att token och vertex färger enas över grafen. Det minsta antalet swappar krävs i optimeringsvarianten av problemet. Vi observerade likheter mellan TSWAP problem och multi-agent sökväg (MAPF) där istället för polletter vi har flera agenter som behöver flyttas från sina nuvarande hörn till ges unika mål hörn. Skillnaden mellan båda problemen består i lokala förhållanden som statsövergångar (svagar/rörelser) måste tillfredsställa. Vi utvecklade två algoritmer för att lösa TSWAP optimalt genom att anpassa två olika tillvägagångssätt till MAPFconflict-baserad sökning (CBS) och SAT-baserad metod som använder beslutsdiagram med flera värden (MDD-SAT). Detta utgör det första försöket att utforma optimala lösningsalgoritmer för TSWAP. Experimentell utvärdering av olika typer av grafer visar att minskningen till SAT-skalan är bättre än CBS i optimal TSWAP-lösning. Det har också visats att TSWAP-fall är lättare att lösa än motsvarande liknande MAPF-fall.
I REF har optimal lösning av TSWAP genom anpassade algoritmer från MPF föreslagits.
Finding Optimal Solutions to Token Swapping by Conflict-Based Search and Reduction to SAT
{'venue': '2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)', 'journal': '2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)', 'mag_field_of_study': ['Computer Science']}