Ängslig sökalgoritm i Python

Denna handledning innehåller kod för att lösa planeringsproblem med en ängslig algoritm. Ängslig sökning är en bättre version av den hierarkiska sökalgoritmen eftersom den kan hitta en lösning snabbare. Ängslig sökning kommer bara att överväga åtgärder på hög nivå som kan nå målet, algoritmen föredrar åtgärder som har fler förfiningar jämfört med åtgärder med färre förfiningar.

En lösning på ett planeringsproblem är en sekvens av åtgärder som tar en agent från ett initialt tillstånd till ett måltillstånd. Ett planeringsproblem beskrivs med ett PDDL (Planning Domain Definition Language). Ett planeringsproblem har ett initialt tillstånd, ett måltillstånd och möjliga åtgärder att genomföra. Tillstånd och möjliga åtgärder läggs till som meningar i en kunskapsbas. Varje möjlig åtgärd har ett funktionsnamn, variabler, förutsättningar och effekter. Ett planeringsproblem kan lösas med framåtsökning (progression) eller bakåtsökning (regression). Framåtsökning startar från det ursprungliga tillståndet och bakåtsökning startar från måltillståndet.

Ängslig sökning behöver en beskrivning av en hierarki av handlingar, från högnivååtgärder (HLA) till primitiva åtgärder. Åtgärder på hög nivå (HLA) förfinas till mer specifika åtgärder, denna process fortsätter tills vi har primitiva åtgärder som inte har några förfiningar. Primitiva åtgärder kommer att inkluderas som steg i den slutliga lösningen på problemet. Ängslig sökning behöver en optimistisk beskrivning som möjligen överskattar den nåbara uppsättningen och en pessimistisk beskrivning som eventuellt underskattar den nåbara uppsättningen. Förmågan att avvisa åtgärder på hög nivå ger ängslig sökning en beräkningsfördel jämfört med hierarkisk sökning.

Jag använder kod från aima-python i den här handledningen (ladda ner paket), dessa moduler innehåller alla nödvändiga klasser och funktioner för en ängslig sökning i Python.

Problem och lösningar

Koden nedan inkluderar 3 problem som definieras som sökproblem. Utmatningen från en körning visas under koden. Varje problem behöver en hierarki av möjliga åtgärder, en optimistisk beskrivning och en pessimistisk beskrivning.

# Import libraries
import aima.utils
import aima.planning

# Get to SFO problem
def get_to_SFO1():

    # Hierarchy of possible actions
    library = {
        'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)', 'Taxi(Home, SFO)'],
        'steps': [['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)'], [], [], []],
        'precond': [['At(Home) & Have(Car)'], ['At(Home)'], ['At(Home) & Have(Car)'], ['At(SFOLongTermParking)'], ['At(Home)']],
        'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(SFOLongTermParking) & ~At(Home)'], ['At(SFO) & ~At(LongTermParking)'], ['At(SFO) & ~At(Home) & ~Have(Cash)']] }

    # Possible actions
    go_SFO = aima.planning.HLA('Go(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
    taxi_SFO = aima.planning.HLA('Taxi(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home) & ~Have(Cash)')
    drive_SFOLongTermParking = aima.planning.HLA('Drive(Home, SFOLongTermParking)', 'At(Home) & Have(Car)','At(SFOLongTermParking) & ~At(Home)' )
    shuttle_SFO = aima.planning.HLA('Shuttle(SFOLongTermParking, SFO)', 'At(SFOLongTermParking)', 'At(SFO) & ~At(LongTermParking)')

    # Create a problem
    problem = aima.planning.RealWorldPlanningProblem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO])

    # Create an initial plan
    optimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & $-At(Home)' ) 
    pessimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & ~At(Home)' )
    initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]

    # Angelic Search
    plan = problem.angelic_search(library, initial_plan)
    print('--- Get to SFO1 problem ---')
    print (plan, '\n')
    print ([x.__dict__ for x in plan])
    print()

# Get to SFO problem
def get_to_SFO2():

    # Hierarchy of possible actions
    library = {
        'HLA': [
            'Go(Home, SFO)',
            'Go(Home, SFO)',
            'Drive(Home, SFOLongTermParking)',
            'Shuttle(SFOLongTermParking, SFO)',
            'Taxi(Home, SFO)'
        ],
        'steps': [
            ['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'],
            ['Taxi(Home, SFO)'],
            [],
            [],
            []
        ],
        'precond': [
            ['At(Home) & Have(Car)'],
            ['At(Home)'],
            ['At(Home) & Have(Car)'],
            ['At(SFOLongTermParking)'],
            ['At(Home)']
        ],
        'effect': [
            ['At(SFO) & ~At(Home)'],
            ['At(SFO) & ~At(Home)'],
            ['At(SFOLongTermParking) & ~At(Home)'],
            ['At(SFO) & ~At(SFOLongTermParking)'],
            ['At(SFO) & ~At(Home)']]}

    # Possible actions
    go_home_sfo1 = aima.planning.HLA('Go(Home, SFO)', precond='At(Home) & Have(Car)', effect='At(SFO) & ~At(Home)')
    go_home_sfo2 = aima.planning.HLA('Go(Home, SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
    drive_home_sfoltp = aima.planning.HLA('Drive(Home, SFOLongTermParking)', precond='At(Home) & Have(Car)', effect='At(SFOLongTermParking) & ~At(Home)')
    shuttle_sfoltp_sfo = aima.planning.HLA('Shuttle(SFOLongTermParking, SFO)', precond='At(SFOLongTermParking)', effect='At(SFO) & ~At(SFOLongTermParking)')
    taxi_home_sfo = aima.planning.HLA('Taxi(Home, SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
    actions = [go_home_sfo1, go_home_sfo2, drive_home_sfoltp, shuttle_sfoltp_sfo, taxi_home_sfo]

    # Create a problem
    problem = aima.planning.RealWorldPlanningProblem(initial='At(Home)', goals='At(SFO)', actions=actions)

    # Create an initial plan
    optimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond='At(Home)', effect='$+At(SFO) & $-At(Home)' ) 
    pessimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond='At(Home)', effect='$+At(SFO) & ~At(Home)' )
    initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]

    # Angelic Search
    plan = problem.angelic_search(library, initial_plan)
    print('--- Get to SFO2 problem ---')
    print(plan, '\n')
    print([x.__dict__ for x in plan])
    print()

# Robot delivery problem
def robot_delivery():

    # Hierarchy of possible actions (Important that steps have different names, see Go and Walk)
    library = {
        'HLA': [
            'Go(MyOffice, MailOffice)',
            'Go(MailOffice, MyOffice)',
            'Walk(MyOffice, Floor)',
            'Walk(MailOffice, Floor)',
            'Walk(Floor, MailOffice)',
            'Walk(Floor, MyOffice)',
            'Pickup(Letter, MailOffice)',
            'Drop(Letter, MyOffice)'
        ],
        'steps': [
            ['Walk(MyOffice, Floor)', 'Walk(Floor, MailOffice)', 'Pickup(Letter, MailOffice)'],
            ['Walk(MailOffice, Floor)', 'Walk(Floor, MyOffice)', 'Drop(Letter, MyOffice)'],
            [],
            [],
            [],
            [],
            [],
            []
        ],
        'precond': [
            ['At(MyOffice) & ~Has(Letter)'],
            ['At(MailOffice) & Has(Letter)'],
            ['At(MyOffice)'],
            ['At(MailOffice)'],
            ['At(Floor)'],
            ['At(Floor)'],
            ['At(MailOffice) & LetterAt(MailOffice)'],
            ['At(MyOffice) & Has(Letter)']
        ],
        'effect': [
            ['At(MailOffice) & ~At(MyOffice) & ~LetterAt(MailOffice)'],
            ['At(MyOffice) & ~At(MailOffice) & LetterAt(MyOffice)'],
            ['At(Floor) & ~At(MyOffice)'],
            ['At(Floor) & ~At(MailOffice)'],
            ['At(MailOffice) & ~At(Floor)'],
            ['At(MyOffice) & ~At(Floor)'],
            ['Has(Letter) & ~LetterAt(MailOffice)'],
            ['~Has(Letter) & LetterAt(MyOffice)']
            ]
        }

    # Possible actions
    myoffice_to_mailoffice = aima.planning.HLA('Go(MyOffice, MailOffice)', precond='At(MyOffice) & ~Has(Letter)', effect='At(MailOffice) & ~At(MyOffice) & ~LetterAt(MailOffice)')
    mailoffice_to_myoffice = aima.planning.HLA('Go(MailOffice, MyOffice)', precond='At(MailOffice) & Has(Letter)', effect='At(MyOffice) & ~At(MailOffice) & LetterAt(MyOffice)')
    myoffice_to_floor = aima.planning.HLA('Walk(MyOffice, Floor)', precond='At(MyOffice)', effect='At(Floor) & ~At(MyOffice)')
    mailoffice_to_floor = aima.planning.HLA('Walk(MailOffice, Floor)', precond='At(MailOffice)', effect='At(Floor) & ~At(MailOffice)')
    floor_to_mailoffice = aima.planning.HLA('Walk(Floor, MailOffice)', precond='At(Floor)', effect='At(MailOffice) & ~At(Floor)')
    floor_to_myoffice = aima.planning.HLA('Walk(Floor, MyOffice)', precond='At(Floor)', effect='At(MyOffice) & ~At(Floor)')
    pickup_letter = aima.planning.HLA('Pickup(Letter, MailOffice)', precond='At(MailOffice) & LetterAt(MailOffice)', effect='Has(Letter) & ~LetterAt(MailOffice)')
    drop_letter = aima.planning.HLA('Drop(Letter, MyOffice)', precond='At(MyOffice) & Has(Letter)', effect='~Has(Letter) & LetterAt(MyOffice)')
    actions = [myoffice_to_mailoffice, mailoffice_to_myoffice, myoffice_to_floor, mailoffice_to_floor, floor_to_mailoffice, floor_to_myoffice, pickup_letter, drop_letter]

    # Angelic Search (Part 1)
    problem = aima.planning.RealWorldPlanningProblem(initial='At(MyOffice) & LetterAt(MailOffice) & ~Has(Letter)', goals='At(MailOffice)', actions=actions)
    optimistic = aima.planning.AngelicHLA('Go(MyOffice, MailOffice)', precond='At(MyOffice)', effect ='$+At(MailOffice) & $-At(MyOffice)') 
    pessimistic = aima.planning.AngelicHLA('Go(MyOffice, MailOffice)', precond='At(MyOffice)', effect ='$+At(MailOffice) & ~At(MyOffice)')
    initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]
    plan = problem.angelic_search(library, initial_plan)
    print('--- Robot delivery part 1 ---')
    print(plan, '\n')
    print([x.__dict__ for x in plan])
    print()

    # Angelic Search (Part 2)
    problem = aima.planning.RealWorldPlanningProblem(initial='At(MailOffice) & Has(Letter)', goals='At(MyOffice)', actions=actions)
    optimistic = aima.planning.AngelicHLA('Go(MailOffice, MyOffice)', precond='At(MailOffice)', effect='$+At(MyOffice) & $-At(MailOffice)') 
    pessimistic = aima.planning.AngelicHLA('Go(MailOffice, MyOffice)', precond='At(MailOffice)', effect='$+At(MyOffice) & ~At(MailOffice)')
    initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]
    plan = problem.angelic_search(library, initial_plan)
    print('--- Robot delivery part 2 ---')
    print(plan, '\n')
    print([x.__dict__ for x in plan])
    print()

# The main entry point for this module
def main():

    # Get to SFO1 problem
    get_to_SFO1()

    # Get to SFO2 problem
    get_to_SFO2()

    # Robot delivery problem
    robot_delivery()

# Tell python to run main method
if __name__ == "__main__": main()
--- Get to SFO1 problem ---
[Drive(Home, SFOLongTermParking), Shuttle(SFOLongTermParking, SFO)]

[{'name': 'Drive', 'args': (Home, SFOLongTermParking), 'precond': [At(Home), Have(Car)], 'effect': [At(SFOLongTermParking), NotAt(Home)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Shuttle', 'args': (SFOLongTermParking, SFO), 'precond': [At(SFOLongTermParking)], 'effect': [At(SFO), NotAt(LongTermParking)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]

--- Get to SFO2 problem ---
[Taxi(Home, SFO)]

[{'name': 'Taxi', 'args': (Home, SFO), 'precond': [At(Home)], 'effect': [At(SFO), NotAt(Home)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]

--- Robot delivery part 1 ---
[Walk(MyOffice, Floor), Walk(Floor, MailOffice), Pickup(Letter, MailOffice)]

[{'name': 'Walk', 'args': (MyOffice, Floor), 'precond': [At(MyOffice)], 'effect': [At(Floor), NotAt(MyOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Walk', 'args': (Floor, MailOffice), 'precond': [At(Floor)], 'effect': [At(MailOffice), NotAt(Floor)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Pickup', 'args': (Letter, MailOffice), 'precond': [At(MailOffice), LetterAt(MailOffice)], 'effect': [Has(Letter), NotLetterAt(MailOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]

--- Robot delivery part 2 ---
[Walk(MailOffice, Floor), Walk(Floor, MyOffice), Drop(Letter, MyOffice)]

[{'name': 'Walk', 'args': (MailOffice, Floor), 'precond': [At(MailOffice)], 'effect': [At(Floor), NotAt(MailOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Walk', 'args': (Floor, MyOffice), 'precond': [At(Floor)], 'effect': [At(MyOffice), NotAt(Floor)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Drop', 'args': (Letter, MyOffice), 'precond': [At(MyOffice), Has(Letter)], 'effect': [NotHas(Letter), LetterAt(MyOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]
Etiketter:

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *