Class: Longjing::Search::FF

Inherits:
Base
  • Object
show all
Includes:
FF
Defined in:
lib/longjing/search/ff.rb

Direct Known Subclasses

FFGreedy

Instance Attribute Summary

Attributes inherited from Base

#statistics

Instance Method Summary collapse

Methods inherited from Base

#initialize, #log_progress, #log_solution, #no_solution, #reset_best_heuristic, #solution

Methods included from Logging

#log, #logger, #logger=

Constructor Details

This class inherits a constructor from Longjing::Search::Base

Instance Method Details

#breadth_first(frontier, best, helpful_actions, goal_set, goal_list) ⇒ Object 



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/longjing/search/ff.rb', line 77

def breadth_first(frontier, best, helpful_actions,
                  goal_set, goal_list)
  known = Hash[frontier.map{|f| [f, true]}]
  until frontier.empty? do
    state = frontier.shift
    statistics.expanded += 1

    log(:exploring, state)
    log_progress(state)

    actions = helpful_actions || @problem.actions(state)
    helpful_actions = nil
    actions.each do |action|
      new_state = @problem.result(action, state)
      statistics.generated += 1
      log(:action, action, new_state)
      if known.include?(new_state)
        logger.debug { "Known state" }
        next
      end

      added_goals = Hash[action.effect.to_a.select{|lit| goal_set.include?(lit)}.map{|k| [k, true]}]
      if solution = @h.extract(goal_list, new_state, added_goals)
        dist = distance(solution)
        new_state.cost = dist
        log(:heuristic, new_state, solution, dist, best)
        if dist < best
          return [new_state, dist, solution[1]]
        else
          known[new_state] = true
          frontier << new_state
        end
      else
        # ignore infinite heuristic state
        logger.debug { "No relaxed solution" }
      end
      statistics.evaluated += 1
    end
  end
  return nil
end

#distance(relaxed) ⇒ Object 



128
129
130
131
132
133
134
135
 
# File 'lib/longjing/search/ff.rb', line 128

def distance(relaxed)
  return Float::INFINITY if relaxed.nil?
  if relaxed[0].empty?
    0
  else
    relaxed[0].map(&:size).reduce(:+)
  end
end

#greedy_search ⇒ Object 



119
120
121
122
123
124
125
 
# File 'lib/longjing/search/ff.rb', line 119

def greedy_search
  reset_best_heuristic
  goal_list = @problem.goal.to_a
  greedy = Greedy.new
  heuristic = lambda {|state| distance(@h.extract(goal_list, state))}
  greedy.search(@problem, heuristic)
end

#hill_climbing(state, goal_list) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/longjing/search/ff.rb', line 52

def hill_climbing(state, goal_list)
  log { "Hill climbing, goal:" }
  log(:facts, goal_list)
  reset_best_heuristic

  best = if relaxed_solution = @h.extract(goal_list, state)
           distance(relaxed_solution)
         end
  logger.debug { "Initial cost: #{best}" }
  return unless best
  state.cost = best
  helpful_actions = relaxed_solution[1]
  goal_set = goal_list.to_set
  until best == 0 do
    state, best, helpful_actions = breadth_first([state],
                                                 best,
                                                 helpful_actions,
                                                 goal_set,
                                                 goal_list)
    return unless state
    logger.debug { "----\nState: #{state}\nCost: #{best}\nPath: #{state.path.map(&:signature).join("\n")}" }
  end
  state
end

#init(problem) ⇒ Object 



23
24
25
26
27
28
29
30
31
32
 
# File 'lib/longjing/search/ff.rb', line 23

def init(problem)
  log { 'Preprocess' }
  @problem = Preprocess.new.execute(problem)
  log { 'Propositionalized problem:' }
  log { "# actions: #{@problem.all_actions.size}" }
  log { 'Initialize graphs' }
  cg = ConnectivityGraph.new(@problem)
  @h = RelaxedGraphPlan.new(cg)
  @ordering = Ordering.new(cg)
end

#search(problem) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/longjing/search/ff.rb', line 34

def search(problem)
  log { 'FF search starts' }
  init(problem)
  log { "Build goal agenda" }
  agenda = @ordering.goal_agenda(@problem)
  log { "Goal agenda:" }
  log(:facts, agenda)
  goal = []
  state = @problem.initial
  agenda.each do |g|
    goal << g
    unless state = hill_climbing(state, goal)
      return greedy_search
    end
  end
  solution(state)
end