Grafplan, algoritm i Python

Jag kommer att använda en grafplan för att lösa klassiska planeringsproblem i denna handledning. En lösning på ett planeringsproblem är en sekvens av åtgärder / handlingar som resulterar i ett måltillstånd (en plan). Automatiserad planering är ett viktigt område inom artificiell intelligens.

En intelligent agent måste kunna skapa planer för att kunna nå ett mål från ett initialt tillstånd. Ett planeringsproblem beskrivs med ett PDDL (Planning Domain Definition Language), ett problem har ett initialt tillstånd, ett måltillstånd och möjliga åtgärder. 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) sökning 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.

En grafplan lägger upprepade gånger till en nivå till en planeringsgraf, en lösning kan hittas om alla mål på en nivå inte är ömsesidigt uteslutande. Algoritmen avslutas om den hittar en lösning som når måltillståndet eller om inga fler nivåer kan läggas till i planeringsgrafen. En planeringsgraf är en riktad graf som är organiserad i nivåer. Två mål är ömsesidigt uteslutande om de tar ut varandra, du kan inte både äta kakan och ha kakan.

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 grafplan i Python.

Problem och lösningar

Den här exempelkoden innehåller tre planeringsproblem och deras lösningar. Jag var tvungen att dela upp robotleveransproblemet i två delar, detta eftersom det var för svårt för algoritmen att få ett brev från postkontoret och föra tillbaka det till mitt kontor: At (Robert, MyOffice) & At (Letter, MyOffice). Det är också ett problem att få algoritmen att släppa brevet på mitt kontor i den andra delen (den hittar en lösning men inte i rätt ordning).

# Import libraries
import aima.utils
import aima.planning
# Air cargo problem
def air_cargo_problem():
    # Planning problem
    problem = aima.planning.PlanningProblem(initial='At(C1, SFO) & At(C2, JFK) & At(P1, SFO) & At(P2, JFK)',
                           goals='At(C1, JFK) & At(C2, SFO)',
                           actions=[aima.planning.Action('Load(c, p, a)',
                                           precond='At(c, a) & At(p, a)',
                                           effect='In(c, p) & ~At(c, a)',
                                           domain='Cargo(c) & Plane(p) & Airport(a)'),
                                    aima.planning.Action('Unload(c, p, a)',
                                           precond='In(c, p) & At(p, a)',
                                           effect='At(c, a) & ~In(c, p)',
                                           domain='Cargo(c) & Plane(p) & Airport(a)'),
                                    aima.planning.Action('Fly(p, f, to)',
                                           precond='At(p, f)',
                                           effect='At(p, to) & ~At(p, f)',
                                           domain='Plane(p) & Airport(f) & Airport(to)')],
                           domain='Cargo(C1) & Cargo(C2) & Plane(P1) & Plane(P2) & Airport(SFO) & Airport(JFK)')
    # Graph plan solution
    solution = aima.planning.GraphPlan(problem).execute()
    print("Air Cargo: {0}".format(aima.planning.linearize(solution)))
    print()
# Drive in romania
def romania():
    # Create a knowledge base
    knowledge_base = [
    aima.utils.expr("Connected(Bucharest,Pitesti)"),
    aima.utils.expr("Connected(Pitesti,Rimnicu)"),
    aima.utils.expr("Connected(Rimnicu,Sibiu)"),
    aima.utils.expr("Connected(Sibiu,Fagaras)"),
    aima.utils.expr("Connected(Fagaras,Bucharest)"),
    aima.utils.expr("Connected(Pitesti,Craiova)"),
    aima.utils.expr("Connected(Craiova,Rimnicu)")
    ]
    # Add rules to knowledge base
    knowledge_base.extend([
     aima.utils.expr("Connected(x,y) ==> Connected(y,x)"),
     aima.utils.expr("At(Sibiu)")
    ])
    # Create a drive action
    drive = aima.planning.Action('Drive(x, y)', precond='At(x) & Connected(x,y)', effect='At(y) & ~At(x)')
    # Create a goal
    goals = 'At(Bucharest)'
    # Graph plan solution
    problem = aima.planning.PlanningProblem(knowledge_base, goals, [drive])
    solution = aima.planning.GraphPlan(problem).execute()
    print("Romania: {0}".format(aima.planning.linearize(solution)))
    print()
# Robot delivery problem
def robot_delivery_problem(initial_state, goals):
    # Create a knowledge base
    kb = [aima.utils.expr("Connected(MyOffice,Floor)"),
          aima.utils.expr("Connected(Floor,MailOffice)"),
          aima.utils.expr("Connected(Floor,Fikarum)"),
          aima.utils.expr("Connected(Fikarum,MailOffice)"),
          aima.utils.expr("Connected(Floor,MyOffice)"),
          aima.utils.expr("Connected(MailOffice,Floor)"),
          aima.utils.expr("Connected(Fikarum,Floor)"),
          aima.utils.expr("Connected(MailOffice,Fikarum)")
          ]
    # Add initial state to the knowledge base
    kb.extend(initial_state)
    # Create actions 
    actions = [aima.planning.Action("Pickup(b, p, r)", 
                                    precond="At(b, r) & At(p, r) & ~Has(b, p)", 
                                    effect="Has(b, p) & ~At(p, r)",
                                    domain="Robot(b) & Packet(p) & Room(r)"),
               aima.planning.Action("Drop(b, p, r)",
                                    precond="At(b, r) & Has(b, p)",
                                    effect="At(p, r) & ~Has(b, p)",
                                    domain="Robot(b) & Packet(p) & Room(r)"),
               aima.planning.Action("Move(b, f, t)",
                                    precond="At(b, f) & Connected(f, t)",
                                    effect="At(b, t) & ~At(b, f)",
                                    domain="Robot(b) & Room(f) & Room(t)")
             ]
    # Create domains
    domains = [aima.utils.expr("Robot(Robert)"), 
               aima.utils.expr("Packet(Letter)"), 
               aima.utils.expr("Room(MyOffice)"), 
               aima.utils.expr("Room(Floor)"), 
               aima.utils.expr("Room(MailOffice)"), 
               aima.utils.expr("Room(Fikarum)")
               ]
    # Create a planning problem
    problem = aima.planning.PlanningProblem(kb, goals, actions, domains)
    # Return the problem
    return problem
# The main entry point for this module
def main():
    # Air cargo problem
    air_cargo_problem()
    # Romania problem
    romania()
    # Robot delivery: first part
    initial_state = [
        aima.utils.expr("At(Robert, MyOffice)"),
        aima.utils.expr("At(Letter, MailOffice)"),
        aima.utils.expr("~Has(Robert, Letter)")
        ]
    goals = [aima.utils.expr("At(Robert, MailOffice)"), aima.utils.expr("Has(Robert, Letter)")]
    problem = robot_delivery_problem(initial_state, goals)
    solution = aima.planning.GraphPlan(problem).execute()
    print("Robot delivery, part 1: {0}".format(aima.planning.linearize(solution)))
    print()
    # Robot delivery: second part
    initial_state = [
        aima.utils.expr("At(Robert, MailOffice)"),
        aima.utils.expr("Has(Robert, Letter)")
        ]
    goals = [aima.utils.expr("At(Robert, MyOffice)")]
    problem = robot_delivery_problem(initial_state, goals)
    solution = aima.planning.GraphPlan(problem).execute()
    print("Robot delivery, part 2: {0}".format(aima.planning.linearize(solution)))
    print()
# Tell python to run main method
if __name__ == "__main__": main()

Air Cargo: [Load(C1, P1, SFO), Load(C2, P2, JFK), Fly(P1, SFO, JFK), Fly(P2, JFK, SFO), Unload(C1, P1, JFK), Unload(C2, P2, SFO)]
Romania: [Drive(Sibiu, Fagaras), Drive(Fagaras, Bucharest)]
Robot delivery, part 1: [Move(Robert, MyOffice, Floor), Move(Robert, Floor, MailOffice), Pickup(Robert, Letter, MailOffice)]
Robot delivery, part 2: [Move(Robert, MailOffice, Floor), Move(Robert, Floor, MyOffice)]