Partiell orderplanerare i Python

Denna handledning visar användningen av en partiell orderplanerare i Python, detta för att lösa klassiska planeringsproblem. En planerare för partiell ordning försöker hitta en lösning på ett planeringsproblem genom att dela upp problemet i delproblem och sedan kombinera delplaner till en komplett plan. En partiell orderplanerare antar att delproblem är oberoende av varandra.

En lösning på ett planeringsproblem är en lista på åtgärder som ska utföras för att nå 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 ett måltillstånd.

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 partiell orderplanerare i Python.

Problem och lösningar

Koden nedan innehåller två problem som jag försöker lösa med en partiell orderplanerare, resultatet från en körning visas under koden. Den partiella orderplaneraren hittar inte en lösning varje gång och den kan hitta fel lösningar. En partiell orderplanerare kan endast användas på problem som har oberoende delproblem.

# Import libraries
import aima.utils
import aima.planning

# Spare tire problem
def spare_tire_problem():

    problem = aima.planning.PlanningProblem(initial='At(Flat, Axle) & At(Spare, Trunk)',
                        goals='At(Spare, Axle) & At(Flat, Ground)',
                        actions=[aima.planning.Action('Remove(obj, loc)',
                                        precond='At(obj, loc)',
                                        effect='At(obj, Ground) & ~At(obj, loc)',
                                        domain='Tire(obj)'),
                                aima.planning.Action('PutOn(t, Axle)',
                                        precond='At(t, Ground) & ~At(Flat, Axle)',
                                        effect='At(t, Axle) & ~At(t, Ground)',
                                        domain='Tire(t)'),
                                aima.planning.Action('LeaveOvernight',
                                        precond='',
                                        effect='~At(Spare, Ground) & ~At(Spare, Axle) & ~At(Spare, Trunk) & \
                                    ~At(Flat, Ground) & ~At(Flat, Axle) & ~At(Flat, Trunk)')],
                        domain='Tire(Flat) & Tire(Spare)')

    # Partial order plan
    plan = aima.planning.PartialOrderPlanner(problem)
    plan.execute()
    print()

# Robot delivery problem
def robot_delivery_problem(initial_state, goals):

    # Create a knowledge base
    kb = "Connected(MyOffice, Floor) & Connected(Floor, MailOffice) & Connected(Floor, Fikarum) & Connected(Fikarum, MailOffice) & Connected(Floor, MyOffice) & Connected(MailOffice, Floor) & Connected(Fikarum, Floor) & Connected(MailOffice, Fikarum)"

    # Add initial state to the knowledge base
    kb += " & " + initial_state

    # Create actions 
    actions = [aima.planning.Action("Pickup(b, p, r)", 
                                    precond="At(b, r) & At(p, r)", 
                                    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 = "Robot(Robert) & Packet(Letter) & Room(MyOffice) & Room(Floor) & Room(MailOffice) & 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():

    # Spare tire problem
    spare_tire_problem()

    # Robot delivery: first part
    initial_state = "At(Robert, MyOffice) & At(Letter, MailOffice)"
    goals = "At(Robert, MailOffice) & Has(Robert, Letter)"
    problem = robot_delivery_problem(initial_state, goals)
    plan = aima.planning.PartialOrderPlanner(problem)
    plan.execute()
    print()

    # Robot delivery: second part
    initial_state = "At(Robert, MailOffice) & Has(Robert, Letter)"
    goals = "At(Robert, MyOffice)"
    problem = robot_delivery_problem(initial_state, goals)
    plan = aima.planning.PartialOrderPlanner(problem)
    plan.execute()
    print()

# Tell python to run main method
if __name__ == "__main__": main()

Probably Wrong
Causal Links
(PutOn(Spare, Axle), At(Spare, Axle), Finish)
(Start, Tire(Spare), PutOn(Spare, Axle))
(Remove(Flat, Axle), NotAt(Flat, Axle), PutOn(Spare, Axle))
(Start, Tire(Flat), Remove(Flat, Axle))
(Start, At(Flat, Axle), Remove(Flat, Axle))
(Remove(Spare, Flat), At(Spare, Ground), PutOn(Spare, Axle))
(Start, Tire(Spare), Remove(Spare, Flat))
(Remove(Flat, Axle), At(Flat, Ground), Finish)

Constraints
Start < PutOn(Spare, Axle)
Remove(Flat, Axle) < PutOn(Spare, Axle)
Start < Remove(Flat, Axle)
Remove(Spare, Flat) < PutOn(Spare, Axle)
PutOn(Spare, Axle) < Finish
Start < Finish
Remove(Flat, Axle) < Finish
Start < Remove(Spare, Flat)

Partial Order Plan
[{Start}, {Remove(Spare, Flat), Remove(Flat, Axle)}, {PutOn(Spare, Axle)}, {Finish}]

Probably Wrong
Causal Links
(Move(Robert, MyOffice, MailOffice), At(Robert, MailOffice), Finish)
(Start, Robot(Robert), Move(Robert, MyOffice, MailOffice))
(Start, Room(MyOffice), Move(Robert, MyOffice, MailOffice))
(Start, Room(MailOffice), Move(Robert, MyOffice, MailOffice))
(Pickup(Robert, Letter, MailOffice), Has(Robert, Letter), Finish)
(Start, Packet(Letter), Pickup(Robert, Letter, MailOffice))
(Start, Room(MailOffice), Pickup(Robert, Letter, MailOffice))
(Start, Robot(Robert), Pickup(Robert, Letter, MailOffice))
(Start, At(Letter, MailOffice), Pickup(Robert, Letter, MailOffice))
(Start, At(Robert, MyOffice), Move(Robert, MyOffice, MailOffice))
(Move(Robert, MyOffice, MailOffice), At(Robert, MailOffice), Pickup(Robert, Letter, MailOffice))

Constraints
Start < Pickup(Robert, Letter, MailOffice)
Start < Finish
Move(Robert, MyOffice, MailOffice) < Pickup(Robert, Letter, MailOffice)
Start < Move(Robert, MyOffice, MailOffice)
Pickup(Robert, Letter, MailOffice) < Finish
Move(Robert, MyOffice, MailOffice) < Finish

Partial Order Plan
[{Start}, {Move(Robert, MyOffice, MailOffice)}, {Pickup(Robert, Letter, MailOffice)}, {Finish}]

Probably Wrong
Causal Links
(Move(Robert, MailOffice, MyOffice), At(Robert, MyOffice), Finish)
(Start, Room(MyOffice), Move(Robert, MailOffice, MyOffice))
(Start, Room(MailOffice), Move(Robert, MailOffice, MyOffice))
(Start, Robot(Robert), Move(Robert, MailOffice, MyOffice))
(Start, At(Robert, MailOffice), Move(Robert, MailOffice, MyOffice))

Constraints
Start < Finish
Move(Robert, MailOffice, MyOffice) < Finish
Start < Move(Robert, MailOffice, MyOffice)

Partial Order Plan
[{Start}, {Move(Robert, MailOffice, MyOffice)}, {Finish}]