Fundamentals of Artificial Intelligence - Lab 1: Expert
Systems
Student: Filipescu Mihail
Verified by: asist. univ. Marusic Diana
In [ ]:
def backward_chain(rules, hypothesis, verbose=False):
"""
Outputs the goal tree from having rules and hyphothesis, works like an "encyclopedia"
"""
length = len(rules)
if length==0:
return hypothesis
tree = OR()
for element in rules:
con = element.consequent()
mat = match(con[0], hypothesis)
if mat is not None and len(mat)>=0:
antec = element.antecedent()
if isinstance(antec, list):
sub = AND()
if isinstance(antec, OR): sub = OR()
for x in antec:
new_tree = backward_chain(rules, populate(x, mat))
sub.append(new_tree)
tree.append(sub)
else:
new_tree = backward_chain(rules, populate(antec, mat))
tree.append(AND(new_tree))
else:
tree.append(hypothesis)
new = simplify(tree)
return new
def print_human_read_backchain(backward_chain):
if isinstance(backward_chain, list):
if isinstance(backward_chain, OR):
print("(", end='')
for o in backward_chain:
print(" or ", end='')
print_human_read_backchain(o)
print(")", end='')
elif isinstance(backward_chain, AND):
print("(", end='')
for a in backward_chain:
print(" and ", end='')
print_human_read_backchain(a)
print("(", end='')
else:
print(backward_chain, end='')
def mixed_questions_gen(rules):
data = []
color_opt = get_color_opt(rules)
print("Tourist has: ")
for i in range(len(color_opt)):
print(i, " ", instantiate(color_opt[i], {'x': 'tourist'}))
num = input("Choose by typing number of color." + "?\n ")
data.append(instantiate(color_opt[int(num)], {'x': 'tourist'}))
data = list(forward_chain(rules, data))
return construct_questions(rules, data)
def get_color_opt(rules):
all_antec = []
for rule in rules:
for ant in rule.antecedent():
m = re.search("^.*skin$", ant)
if m != None:
all_antec.append(m.group(0))
return list(set(all_antec))
def construct_questions(rules, data = []):
final_states = get_all_final(rules)
noLeafes = []
leafes = get_all_leafes(rules)
while True:
goal_reached = False
counter = 0
for leaf in leafes:
# print(leaf,is_actual(leaf, data, rules, noLeafes))
if data and not is_actual(leaf, data, rules, noLeafes):
counter = counter + 1
continue
dataElement = instantiate(leaf, {'x': 'tourist'})
response = check_response(input(dataElement + "?\n "))
if response:
data.append(dataElement)
data = list(forward_chain(rules, data))
if len(set(data).intersection(final_states)) > 0:
goal_reached = True #goal reached
break
elif not response:
noLeafes.append(leaf)
if counter >= len(leafes) or goal_reached:
break
return data
def print_the_goal(data, rules):
final_states = get_all_final(rules)
goal = set(data).intersection(final_states)
if len(goal) > 0:
print(goal)
else:
print("Could not identify the tourist, it must be a Looney!")
def get_all_final(rules):
final_states = []
for rule in rules:
final_states.append(rule.consequent()[0])
all_antec = []
for rule in rules:
for ant in rule.antecedent():
all_antec.append(ant)
final_states = list(set(final_states).difference(set(all_antec)))
for i in range(len(final_states)):
final_states[i] = instantiate(final_states[i], {'x': 'tourist'})
return set(final_states)
def get_all_leafes(rules):
leafes = []
for rule in rules:
ant = rule.antecedent()
for x in ant:
if check_if_leaf(x, rules):
leafes.append(x)
return list(dict.fromkeys(leafes))
def is_actual(leaf, data, rules, noLeafes):
found_rules = []
for fact in data:
found_rules = found_rules + get_all_rules_with_expr(fact, rules)
if is_present_in_rules(leaf, found_rules) and not is_present_in_data(leaf, data) and
not was_asked_before(leaf, noLeafes):
return True
return False
def was_asked_before(leaf, noLeafes):
for l in noLeafes:
if match(leaf, l) != None:
return True
return False
def is_present_in_rules(expr, rules):
for rule in rules:
if is_expr_present_in_rule(expr, rule):
return True
return False
def is_present_in_data(expr, data):
for fact in data:
if match(fact, populate(expr, {"x": "tourist"})) != None:
return True
return False
def get_all_rules_with_expr(expr, rules):
new_rules = []
for rule in rules:
if is_expr_present_in_rule(expr, rule):
new_rules.append(rule)
return new_rules
def is_expr_present_in_rule(expr, rule):
for ant in rule.antecedent():
if match(ant, expr) != None:
return True
return False
def get_children_from_parent(parent, rules):
children = []
for rule in rules:
for ant in rule.antecedent():
if match(parent.consequent()[0], ant) != None:
children.append(rule)
return children
def check_response(response):
if response == "yes":
return True
elif response == "no":
return False
else:
return None
def check_if_leaf(condition, rules):
for rule in rules:
if match(condition, rule.consequent()[0]) != None:
return False
return True
Task 1 - Defining 5 types of tourists:
Task 2 - Implementing the rules from .....
In [ ]:
TOURISTS_RULES = (
IF ( AND( '(?x) has yellow skin',
'(?x) has pointy ears'),
THEN( '(?x) is an Elf' )),
IF ( AND( '(?x) has good magica affinity',
'(?x) has dark skin'),
THEN( '(?x) is an Elf' )),
IF ( AND( '(?x) is an Elf',
'(?x) has heat tolerance'),
THEN( '(?x) is a Dunmer' )),
IF ( AND( '(?x) is an Elf',
'(?x) lives in forest'),
THEN( '(?x) is a Bosmer' )),
IF ( AND( '(?x) has dark skin',
'(?x) has a skimitar'),
THEN( '(?x) is a Humman' )),
IF ( AND( '(?x) has non-pointy ears',
'(?x) has white skin'),
THEN( '(?x) is a Humman' )),
IF ( AND( '(?x) is a Humman',
'(?x) lives in desert'),
THEN( '(?x) is a Redgard' )),
IF ( AND( '(?x) is a Humman',
'(?x) loves epic fights',
'(?x) has cold tolerance'),
THEN( '(?x) is a Nord' )),
IF ( AND( '(?x) is good in trading',
'(?x) is a Humman',
'(?x) has a sweet tongue'),
THEN( '(?x) makes a lot of money' )),
IF ( AND( '(?x) makes a lot of money',
'(?x) has a lot of stamina',
'(?x) is a Humman'),
THEN( '(?x) is an Imperial' )),
)
Task 3
In [ ]:
data = forward_chain(TOURISTS_RULES, TOURISTS_DATA)
print(data)
In [ ]:
Output: ('tim has dark skin', 'tim has good magica affinity', 'tim has heat tolerance', '
tim is a Dunmer', 'tim is an Elf')
Task 4
In [ ]:
def backward_chain(rules, hypothesis, verbose=False):
"""
Outputs the goal tree from having rules and hyphothesis, works like an "encyclopedia"
"""
length = len(rules)
if length==0:
return hypothesis
tree = OR()
for element in rules:
con = element.consequent()
mat = match(con[0], hypothesis)
if mat is not None and len(mat)>=0:
antec = element.antecedent()
if isinstance(antec, list):
sub = AND()
if isinstance(antec, OR): sub = OR()
for x in antec:
new_tree = backward_chain(rules, populate(x, mat))
sub.append(new_tree)
tree.append(sub)
else:
new_tree = backward_chain(rules, populate(antec, mat))
tree.append(AND(new_tree))
else:
tree.append(hypothesis)
new = simplify(tree)
return new
Task 5-6-7
In [ ]:
def print_human_read_backchain(backward_chain):
if isinstance(backward_chain, list):
if isinstance(backward_chain, OR):
print("(", end='')
for o in backward_chain:
print(" or ", end='')
print_human_read_backchain(o)
print(")", end='')
elif isinstance(backward_chain, AND):
print("(", end='')
for a in backward_chain:
print(" and ", end='')
print_human_read_backchain(a)
print("(", end='')
else:
print(backward_chain, end='')
def mixed_questions_gen(rules):
data = []
color_opt = get_color_opt(rules)
print("Tourist has: ")
for i in range(len(color_opt)):
print(i, " ", instantiate(color_opt[i], {'x': 'tourist'}))
num = input("Choose by typing number of color." + "?\n ")
data.append(instantiate(color_opt[int(num)], {'x': 'tourist'}))
data = list(forward_chain(rules, data))
return construct_questions(rules, data)
def get_color_opt(rules):
all_antec = []
for rule in rules:
for ant in rule.antecedent():
m = re.search("^.*skin$", ant)
if m != None:
all_antec.append(m.group(0))
return list(set(all_antec))
def construct_questions(rules, data = []):
final_states = get_all_final(rules)
noLeafes = []
leafes = get_all_leafes(rules)
while True:
goal_reached = False
counter = 0
for leaf in leafes:
# print(leaf,is_actual(leaf, data, rules, noLeafes))
if data and not is_actual(leaf, data, rules, noLeafes):
counter = counter + 1
continue
dataElement = instantiate(leaf, {'x': 'tourist'})
response = check_response(input(dataElement + "?\n "))
if response:
data.append(dataElement)
data = list(forward_chain(rules, data))
if len(set(data).intersection(final_states)) > 0:
goal_reached = True #goal reached
break
elif not response:
noLeafes.append(leaf)
if counter >= len(leafes) or goal_reached:
break
return data
def print_the_goal(data, rules):
final_states = get_all_final(rules)
goal = set(data).intersection(final_states)
if len(goal) > 0:
print(goal)
else:
print("Could not identify the tourist, it must be a Looney!")
def get_all_final(rules):
final_states = []
for rule in rules:
final_states.append(rule.consequent()[0])
all_antec = []
for rule in rules:
for ant in rule.antecedent():
all_antec.append(ant)
final_states = list(set(final_states).difference(set(all_antec)))
for i in range(len(final_states)):
final_states[i] = instantiate(final_states[i], {'x': 'tourist'})
return set(final_states)
def get_all_leafes(rules):
leafes = []
for rule in rules:
ant = rule.antecedent()
for x in ant:
if check_if_leaf(x, rules):
leafes.append(x)
return list(dict.fromkeys(leafes))
def is_actual(leaf, data, rules, noLeafes):
found_rules = []
for fact in data:
found_rules = found_rules + get_all_rules_with_expr(fact, rules)
if is_present_in_rules(leaf, found_rules) and not is_present_in_data(leaf, data) and
not was_asked_before(leaf, noLeafes):
return True
return False
def was_asked_before(leaf, noLeafes):
for l in noLeafes:
if match(leaf, l) != None:
return True
return False
def is_present_in_rules(expr, rules):
for rule in rules:
if is_expr_present_in_rule(expr, rule):
return True
return False
def is_present_in_data(expr, data):
for fact in data:
if match(fact, populate(expr, {"x": "tourist"})) != None:
return True
return False
def get_all_rules_with_expr(expr, rules):
new_rules = []
for rule in rules:
if is_expr_present_in_rule(expr, rule):
new_rules.append(rule)
return new_rules
def is_expr_present_in_rule(expr, rule):
for ant in rule.antecedent():
if match(ant, expr) != None:
return True
return False
def get_children_from_parent(parent, rules):
children = []
for rule in rules:
for ant in rule.antecedent():
if match(parent.consequent()[0], ant) != None:
children.append(rule)
return children
def check_response(response):
if response == "yes":
return True
elif response == "no":
return False
else:
return None
def check_if_leaf(condition, rules):
for rule in rules:
if match(condition, rule.consequent()[0]) != None:
return False
return True
Conclusions:
For this lab, I learned how the expert system works by deducting the solution from given facts. It was quite
curious to play around with the basic structure of Goal tree. For me, the backward -chaining was the most
interesting part, while the generation of questions was a little bit more tedious an challenging. All things
considered, by completing this lab, I developed further my programming skills and a more in detpth Expert sys
understanding.
In [ ]:
# required part
