Class: Longjing::FF::Ordering

Inherits:
Object
  • Object
show all
Defined in:
lib/longjing/ff/ordering.rb

Instance Method Summary collapse

Constructor Details

#initialize(connectivity_graph) ⇒ Ordering

Returns a new instance of Ordering.



4
5
6
7
8
 
# File 'lib/longjing/ff/ordering.rb', line 4

def initialize(connectivity_graph)
  @actions = connectivity_graph.actions
  @add2actions = connectivity_graph.add2actions
  @del2actions = connectivity_graph.del2actions
end

Instance Method Details

#compute_transitive_closure(nodes, graph) ⇒ Object 



110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/longjing/ff/ordering.rb', line 110

def compute_transitive_closure(nodes, graph)
  nodes.each do |j|
    nodes.each do |i|
      if graph[i][j]
        nodes.each do |k|
          if graph[j][k]
            graph[i][k] = true
          end
        end
      end
    end
  end
end

#da(f) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/longjing/ff/ordering.rb', line 10

def da(f)
  if actions = @add2actions[f]
    set = Hash[actions[0].del.map{|l|[l, true]}]
    actions[1..-1].inject(set) do |memo, action|
      n = {}
      action.del.each do |f|
        if memo.include?(f)
          n[f] = true
        end
      end
      n
    end
  else
    {}
  end
end

#goal_agenda(prob) ⇒ Object 



76
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
 
# File 'lib/longjing/ff/ordering.rb', line 76

def goal_agenda(prob)
  g = Hash.new{|h,k|h[k]={}}
  list = prob.goal.to_a
  list.each do |a|
    list.each do |b|
      next if a == b
      g[a][b] = !heuristic_ordering(b, a)
    end
  end

  compute_transitive_closure(list, g)

  # in&out edges
  degree = Hash.new{|h,k| h[k]=0}
  hits = Hash.new{|h,k| h[k]=0}
  list.each do |a|
    list.each do |b|
      next if a == b
      if g[a][b]
        degree[a] -= 1
        degree[b] += 1
        hits[a] += 1
        hits[b] += 1
      end
    end
  end

  # order by increasing degree
  # disconnected at the end
  list.sort_by do |a|
    hits[a] == 0 ? Float::INFINITY : degree[a]
  end
end

#heuristic_fixpoint_reduction(a) ⇒ Object 



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/longjing/ff/ordering.rb', line 42

def heuristic_fixpoint_reduction(a)
  facts = da(a)
  del_a_actions = @del2actions[a] || {}
  actions = {}
  @actions.each do |action|
    next if del_a_actions.include?(action)
    next if action.pre.any?{|l| facts.include?(l)}
    actions[action] = true
  end

  fixpoint = false
  while(!fixpoint) do
    fixpoint = true
    facts.keys.each do |f|
      if possibly_achievable_atoms(f, actions)
        facts.delete(f)
        actions = {}
        @actions.each do |action|
          next if del_a_actions.include?(action)
          next if action.pre.any?{|l| facts.include?(l)}
          actions[action] = true
        end
        fixpoint = false
      end
    end
  end
  [facts, actions]
end

#heuristic_ordering(a, b) ⇒ Object 



71
72
73
74
 
# File 'lib/longjing/ff/ordering.rb', line 71

def heuristic_ordering(a, b)
  facts, actions = heuristic_fixpoint_reduction(a)
  possibly_achievable_atoms(b, actions)
end

#possibly_achievable_atoms(p, action_set) ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/longjing/ff/ordering.rb', line 27

def possibly_achievable_atoms(p, action_set)
  if actions = @add2actions[p]
    actions.any? do |action|
      next unless action_set.include?(action)
      action.pre.all? do |lit|
        if acs = @add2actions[lit]
          acs.any? do |a|
            action_set.include?(a) && a != action
          end
        end
      end
    end
  end
end