สถานะเริ่มต้น
สถานะเป้าหมาย
ตารางทั้งหมดมี 8 ช่อง (ไม่นับช่องว่าง) ถ้าช่องใดตรงกับสถานะเป้าหมายได้1คะแนน ถ้าไม่ตรงได้0 เช่นคะแนนในสถานะเริ่มต้นในปัจจุบันคือ4คะแนนเพราะมีตาราง3457ตรงกับสถานะเป่้าหมาย เมื่อมีการเลื่อนช่องว่าง1ครั้ง ก็จะคิดคะแนน1ครั้ง เช่นจากสถานะเริ่มต้น ถ้าเลื่อนช่องว่างขึ้นข้างบน สถานะใหม่จะมี 5คะแนน เพราะช่องตรงกับเป้าหมายมี 5ช่องคือ 34567(ไม่นับช่องว่าง)
การเปลี่ยนสถานะทำให้เกิดสถานะใหม่สูงสุด 4 สถานะ เพราะทิศทางการเลื่อนของช่องว่างมีได้สูงสุด 4 ทิศทาง ในการเลือกว่าสถานะใหม่อันไหนดีที่สุดให้พิจารณษจากคะแนนที่ได้ สถานะใหม่ที่เลือกได้นี้ ทำให้การเลื่อนช่องว่างอีก แล้วทำการคำนวณคะแนนที่ได้ออกมา ทำอย่างงี้เรื่อยๆจนกว่าสถานะใหม่มี 8คะแนน
การแก้ปัญหาจากสถานะเริ่มต้น แล้วเลื่อนช่องว่างขึ้น ซ้ายและขวา(เลื่อนลงไม่ได้)แล้วทำการเลื่อนช่องว่างไปซ้าย ขึ้น และขวา(ไม่เลื่อนลงเพราะจะทำให้สถานะใหม่กลับสู้เริ่มต้นอีก)ทำการเลื่อนช่องว่างไปทำเช่นนี้ซ้ำจนได้ผลลัพธ์ออกมา
วิธีการแก้ปัญหา
สมมุติ ปริภูมิปัญหา คือกล่องดำที่เต็มไปด้วยสถานะต่างๆมากมายที่สร้างขึ้นมาด้วยกฎ รวมถึงเป้าหมายก็อยู่ในนั้นด้วยการแก้ปัญหา คือเราค้นหาตำแหน่งเป้าหมายในปริภูมิปัญหานั้น หาเส้นทางเป้าหมายย้อนกลับไปทางเริ่มต้น กระบวนการของคอมพิวเตอร์จะทำการแก้ปัญหาคำตอบ search การแก้ปัญหาต้องพิจารณาคือ- การค้นหาคำตอบ
- การแสดงความรู้
- กระบวนการในการเลือก
การค้นหาคำตอบ
เป็นการกำหนดทิสทางสำหรับการค้นหาและรูปแบบโครงสร้างข้อมูลที่ใช้สำหรับการค้นหา เป็นการกำหนดลำดับของการพิจารณาโหนดหรือสถานะต่างๆ ในโครงสร้างข้อมูลสำหรับการค้นหาคำตอบ
การสร้างรูปแบบเครื่อข่ายข้อมูลกราฟ ดีกว่าต้นไม้ เพราะจะประหยัดพื้นที่หน่วยความจภำ การค้นหาข้อมูลทำได้เร็วกว่า ข้อเสีย ทำให้เชื่อมต่อของข้อมูลทำได้ยาก ใช้เวลาในการเชื่อมต่อข้อมูลนานกว่า ดังนั้นการออกแบบโครงสร้างบางครั้งจึงนิยมสร้างเป้นต้นไม้ก่อนแล้วค่อยเปลี่ยนเป็นกราฟ
การแสดงความรู้
Knowledge Representation เป้นวิธ๊การแสดงความรู้ในการแก้ปัญหาให้อยู่ในรูปแบบที่คอมพิวเตอร์ประมวลผลได้ การแสดงคสามรู้นี้จุะอยู่ในรูปประโยค และจะต้องสอดคล้องกันทั้งในแง่ของไวยากรณ์ ท Syntax และความหมาย Semantic
เงื่อนไข-->ข้อสรุป
ในกรณ๊ที่ความรู้ไม่ใช่ตัวเลข เป็นobjectและfact ที่มีความสัมพันธ์กัน เช่น ความรู้ "Plant is on the table พืชอยู่บนโต็ะ"
จะมีobject 2 ตัว พืชและโต๊ะ มีonแสดงถึงความสัมพันธ์การแสะดงความรู้แบบนี้จะมีการกล่าวถึงต่อไปอย่างละเอียด
ON(plant,table):plant is on the table
IN(table,room):table is in the room
UNDER (table,window)table is under the window
อย่างไรการแสดงความรู้มีสิ่งที่ควรคำนึงถึง
1.รวมความรู้เป็นหนึ่งเดียวกันได้อย่างไร เช่น ถ้าอธิบายลักษณะห้องห้องหนึ่ง ห้องนี้มีโต๊ะตั้งไว้ใต้หน้าต่าง table is under the window แล้ววันหนึ่งมีการเปลี่ยนฐานความรู้ว่า CENTER (table,room)ในระบบแสดงความรู้มีวิธีการอย่างไรที่จะแจ้งให้ทราบว่าUNDER (table,window) ไม่ได้เพราะในเมื่อโต๊ะมาอยู่กลางห้องก็เป็นไปไม่ได้ทีโต๊ะจะอยู่ใต้หน้าต่างด้วย
2.จัดลำดับให้ค้นหาง่าย เช่น ถ้าเติมABOVE(ceiling,floor)เข้าไปในฐานความรู้ ใส่ตรงไหนที่จะไม่ต้องบอกทุกครั้งเมื่อมีการอ้างถึงว่า เพดานอยู่เหนือพื้น
ทั้งหมดที่กล่าวมานี้เป็นการแสดงความรู้ด้วยเฟรม(frame)
เงื่อนไข-->ข้อสรุป
ในกรณ๊ที่ความรู้ไม่ใช่ตัวเลข เป็นobjectและfact ที่มีความสัมพันธ์กัน เช่น ความรู้ "Plant is on the table พืชอยู่บนโต็ะ"
จะมีobject 2 ตัว พืชและโต๊ะ มีonแสดงถึงความสัมพันธ์การแสะดงความรู้แบบนี้จะมีการกล่าวถึงต่อไปอย่างละเอียด
ON(plant,table):plant is on the table
IN(table,room):table is in the room
UNDER (table,window)table is under the window
อย่างไรการแสดงความรู้มีสิ่งที่ควรคำนึงถึง
1.รวมความรู้เป็นหนึ่งเดียวกันได้อย่างไร เช่น ถ้าอธิบายลักษณะห้องห้องหนึ่ง ห้องนี้มีโต๊ะตั้งไว้ใต้หน้าต่าง table is under the window แล้ววันหนึ่งมีการเปลี่ยนฐานความรู้ว่า CENTER (table,room)ในระบบแสดงความรู้มีวิธีการอย่างไรที่จะแจ้งให้ทราบว่าUNDER (table,window) ไม่ได้เพราะในเมื่อโต๊ะมาอยู่กลางห้องก็เป็นไปไม่ได้ทีโต๊ะจะอยู่ใต้หน้าต่างด้วย
2.จัดลำดับให้ค้นหาง่าย เช่น ถ้าเติมABOVE(ceiling,floor)เข้าไปในฐานความรู้ ใส่ตรงไหนที่จะไม่ต้องบอกทุกครั้งเมื่อมีการอ้างถึงว่า เพดานอยู่เหนือพื้น
ทั้งหมดที่กล่าวมานี้เป็นการแสดงความรู้ด้วยเฟรม(frame)
การค้นหา
จุดเริ่มต้นคือstart state พิจารนาสถานะเป้าหมาย goal state ถ้าไม่ใช่ต้องหาเป้าหมายต่อไป การค้นหาต้องค้นหาจากระยะทางที่ใกล้ที่สุดก่อน ทำให้ค้นหาง่ายขึ้น
ส่วนประกอบการค้นหา
โครงสร้างข้อมูลของต้นไม้ค้นหาSearch tree ต้องประกอบด้วยจุดต่อnodeแต่ละจุดต่อประกอบด้วยมั้ง
1.state=สถานะที่ต้องมีการเชื่อมโยง
2.parent node=จุดต่อม่าย
3.operation=การดำเนินการ
4.depth node=ความลึกของจุดต่อ จำนวนชั้นจุดต่อ
5.path cost=ค่าระยะทาง
1.state=สถานะที่ต้องมีการเชื่อมโยง
2.parent node=จุดต่อม่าย
3.operation=การดำเนินการ
4.depth node=ความลึกของจุดต่อ จำนวนชั้นจุดต่อ
5.path cost=ค่าระยะทาง
การวัดความสำเร็จการค้นหา
ประกอบด้วยเกณฑ์ข้อสรุป
1.Completeness ค้นพบคำตอบไหม?
2.Time complexity เวลาค้นหา
3.Space complexity จำนวนหน่วยความจำที่ใช้ในการจำจุดต่อจุด
4. Optimality มีประสิทธิภาพ?
1.Completeness ค้นพบคำตอบไหม?
2.Time complexity เวลาค้นหา
3.Space complexity จำนวนหน่วยความจำที่ใช้ในการจำจุดต่อจุด
4. Optimality มีประสิทธิภาพ?
ค้นหามี2แบบ ค้นหาแบบสม่ำเสมอ การค้นหาแบบแจ้งให้ทราบ
การค้นหาแบบสม่ำเสมอ uniform search
1.การค้นหาแบบกว้าง breadth first search เป็นการค้นหาเริ่มจากราก ค้นหาไปยังจุดต่อลูก ถ้าความสูงของต้นไม้มีค่าเท่ากับ dการค้นหาจะd+1 สามารถเขียนโปรแกรมโดยใช้คิว ค้นหาจะประสบความสำเร็จต่อเมื่อสถานะที่ต้องการค้นหาอยู่แบบตื้นๆ ค้นหาแนวกว้างจะสมบูรณ์ ต่อเมื่อจำนวนครั้งมีไม่มากนัก ขึ้นอยู่กับชั้นของจุดต่อ
1.การค้นหาแบบกว้าง breadth first search เป็นการค้นหาเริ่มจากราก ค้นหาไปยังจุดต่อลูก ถ้าความสูงของต้นไม้มีค่าเท่ากับ dการค้นหาจะd+1 สามารถเขียนโปรแกรมโดยใช้คิว ค้นหาจะประสบความสำเร็จต่อเมื่อสถานะที่ต้องการค้นหาอยู่แบบตื้นๆ ค้นหาแนวกว้างจะสมบูรณ์ ต่อเมื่อจำนวนครั้งมีไม่มากนัก ขึ้นอยู่กับชั้นของจุดต่อ
2. การค้นหาแนวลึก depth first searchโดยเริ่มจากจุดราก แล้วค้นหาไปยังลูกที่ลึกที่สุดทางซ้ายมือก่อน แล้วค้นต่อลูกทางขวามือ bเป็นจำนวนจุดต่อในแต่ละชั้นและmเท่ากับจำนวนชั้น
Depth first search ใช้หน่วยความจำน้อยกว่าการค้นหาในbreadth first search เพราะว่ามีการเก็บข้อมูลเฉพาะในวิถีที่พิจารณาเท่านั้น ในขณะที่การค้นหาแนวกว้างต้องเก็บข้อมูลทุกจุดต่อในแต่ละระดับครั้งละ 1ระดับ ทุกสถานะก่อนจะพิจารณาระดับหนึ่ง การค้นหาแนวกว้างจะไม่ถูกกักอยู่ในสถานที่วนซ้ำ เหมือนกันการค้นหาแนวลึก เกิดได้ถ้าถ้าไม่มีการเก็บข้อมูลของสถานะที่ได้ผ่านมาแล้ว แต่ถ้าหากปัญหานั้นมีผลเฉลยนั้นมีหลายผลเฉลย การค้นหาแนวกว้างจะได้ผลเฉลยที่ระยะที่สั้นที่สุด ซึ่งระยะทางจำนวนใช้กฎในขณะที่การค้นหาแนวลึกได้ผลเฉลี่ยที่มากกว่า เพราะว่าเพราะว่าผลเฉลยที่ระยะสั้นที่สุดไม่ได้ถูกนำพิจารณาในการค้นหานั้น
3.การค้นหาจำกัดความลึก depth limited search เป็นการกำหนดค่าความลึก ของเส้นทางเอาไว้โดยกำหนดในขั้นตอนวิธีในขณะค้นหาเลยก็ได้ เช่น แผนที่ประเทศไทย77จังหวัด ค่าสูงสุดของการค้นหาคือ19ชั้น จากการกำหนดนี้รับรองว่าต้องค้นพบผลลัพธ์ แต่จะไม่รองรับว่าจะค้นพบระยะทางที่สั้นที่สุดก่อน ซึ่งถ้ากำหนดระยะทางสิ้นสุดสั้นเกินไปก็จะค้นไม่พบ เวลาและการใช้เนื้อที่การค้นคล้ายกับก่รค้นหาแนวลึก
Depth first search ใช้หน่วยความจำน้อยกว่าการค้นหาในbreadth first search เพราะว่ามีการเก็บข้อมูลเฉพาะในวิถีที่พิจารณาเท่านั้น ในขณะที่การค้นหาแนวกว้างต้องเก็บข้อมูลทุกจุดต่อในแต่ละระดับครั้งละ 1ระดับ ทุกสถานะก่อนจะพิจารณาระดับหนึ่ง การค้นหาแนวกว้างจะไม่ถูกกักอยู่ในสถานที่วนซ้ำ เหมือนกันการค้นหาแนวลึก เกิดได้ถ้าถ้าไม่มีการเก็บข้อมูลของสถานะที่ได้ผ่านมาแล้ว แต่ถ้าหากปัญหานั้นมีผลเฉลยนั้นมีหลายผลเฉลย การค้นหาแนวกว้างจะได้ผลเฉลยที่ระยะที่สั้นที่สุด ซึ่งระยะทางจำนวนใช้กฎในขณะที่การค้นหาแนวลึกได้ผลเฉลี่ยที่มากกว่า เพราะว่าเพราะว่าผลเฉลยที่ระยะสั้นที่สุดไม่ได้ถูกนำพิจารณาในการค้นหานั้น
3.การค้นหาจำกัดความลึก depth limited search เป็นการกำหนดค่าความลึก ของเส้นทางเอาไว้โดยกำหนดในขั้นตอนวิธีในขณะค้นหาเลยก็ได้ เช่น แผนที่ประเทศไทย77จังหวัด ค่าสูงสุดของการค้นหาคือ19ชั้น จากการกำหนดนี้รับรองว่าต้องค้นพบผลลัพธ์ แต่จะไม่รองรับว่าจะค้นพบระยะทางที่สั้นที่สุดก่อน ซึ่งถ้ากำหนดระยะทางสิ้นสุดสั้นเกินไปก็จะค้นไม่พบ เวลาและการใช้เนื้อที่การค้นคล้ายกับก่รค้นหาแนวลึก
4.การค้นหาแบบทีดีที่สุดก่อน(ฺBest-first search)เป็นกระบวนการค้นหาข้อมูลที่นำเอาข้อดีbreadth first searchกับdepth first searchมารวมกันเป็นวิธีการเดียว ดดยแต่ละขั้นค้นหาในโหนดลูกนั้น เลือกเอาโหนดทที่ดีที่สุด(most promising)
ความฉลาดไม่จำเป็นต้องมีข้อมูลจำนวนมากเสมอไป แต่เกี่ยวข้องกับการแทนความรู้ต่างๆลงในโปรแกรมและให้เหตุผลของโปรแกรม การแทนความรู้ เป็นคำพื้นฐานที่ใช้อ้างถึงกระบวนการแทนโดยคอมพิวเตอร์ยุคใหม่ เป็นส่วนหนึ่งของอ็อบเจกต์ต่างๆและอ้างถึงอ็อบเจกต์นั้น ความรู้ที่แทนได้จะเก็บไว้ในคอมพิวเตอร์และทำให้คอมพิวเตอร์หาข้อสรุปได้
เทคนิคการแทนความรู้
3ชนิดคือ
3ชนิดคือ
1.การแทนความรู้เชิงตรรกะ logic-based representation
กระบวนการในการนำข้อเท็จจริง เข้าไปประมวลตรรกะแล้ว จะได้เป็นผลลัพธ์ออกมา ถ้าค่าความจริงเป็นจริงจะสามารถพิสูจน์ได้ทางคณิตศาสตร์ว่าผลที่ได้จะต้องจริง ตรรกศาสตร์ที่ใช้แทนความรู้แบ่งออกเป็น2ชนิด คือ ตรรศาสตร์ประพจน์ และแคลคูลัสภาคแสดง
1.1ตรรกศาสตร์ประพจน์(propositional logic) เป้นประโยคที่กล่าวถึงสิ่งใดสิ่งหนึ่งที่มีลักษณะเฉพาะ (ประโยคอะตอม)
กฎข้อที่1 ประพจน์เป็นกฎ
กฎข้อที่2 ถ้า P และ Q เป็นกฎแล้วต่อไปนี้เป็นกฎ
เช่น it is raining and pussy is outside-->pussy gets wet
ถ้าใส่วงเล็บจะแตกต่างกัน
1.(it is raining and pussy is outside)-->pussy gets wet
ถ้าใส่วงเล็บจะแตกต่างกัน
1.(it is raining and pussy is outside)-->pussy gets wet
2.it is raining and (pussy is outside-->pussy gets wet)
ประโยค1คือถ้าฝนตกจริงและแมวที่ชื่อพุชซี่อยู่ข้างนอกจริงพุชซี่จะต้องเปียก
ประโยค2คือฝนตกแล้วขณะนี้จริงถ้าพุชซี่อยู่ข้างนอกพุซซี่ขะเปียก
ตารางค่าความจริงแบ่งออกเป็น3ประเภท
1.สัจนินันดร์(tautology)จะได้ค่าความเป็นจริงเป็นจริงเสมอในทุกกรณ๊
2.คอนทินเจนต์(contingent)ได้ค่าความเป็นจริงที่มีโอกาศจริงบ้างเท็จบ้าง
3.อินคอนซิเทนต์(inconsistent)ได้ค่าความจริงที่ไม่มีทางเป็นจริงหมด
1.2 แคลคูลัสภาคแสดง(predicate calculus)
or bird(tweety)
is a (tweety ,bird)
ลองพิจารณา "If tweety files then tweety is a bird.Tweety flies. Therefore tweety is a bird"
2.คอนทินเจนต์(contingent)ได้ค่าความเป็นจริงที่มีโอกาศจริงบ้างเท็จบ้าง
3.อินคอนซิเทนต์(inconsistent)ได้ค่าความจริงที่ไม่มีทางเป็นจริงหมด
1.2 แคลคูลัสภาคแสดง(predicate calculus)
or bird(tweety)
is a (tweety ,bird)
ลองพิจารณา "If tweety files then tweety is a bird.Tweety flies. Therefore tweety is a bird"
2.การแทนความรู้เชิงอ็อบเจกต์object-based representation
3.การแทนความรู้เชิงกฎrule-based representation
ชนิดของ Agent
- Simple reflex agents
- Model-based agents
- Goal-based agents
- Utility-based agents
- Learning agents
Simple reflex agents
- การดำเนินการบนพื้นฐานของ Percept ปัจจุบัน (ไม่มีประวัติ)
- ขึ้นอยู่กับกฎสภาพการกระทำ (ถ้ามีแล้ว)
- ที่เรียบง่าย แต่มีสติปัญญาที่ จำกัด มากEx: Thermostat
Model-based agents
ติดตามประวัติศาสตร์ Percept
- สร้าง "รูปแบบ"
- ตามยังคงอยู่ในการปกครองถ้าแล้ว
Ex: หุ่นยนต์เครื่องดูดฝุ่น - ครอบคลุมพื้นที่ทั้งหมด
Goal-based agents
- มีข้อมูลเกี่ยวกับสถานการณ์บางอย่างที่เป็นที่พึงประสงค์
- ท่ามกลางความเป็นไปได้หลายเลือกหนึ่งซึ่งถึงเป้าหมายของรัฐ
Ex: ระบบตรวจสอบคำที่ไม่ดี - ตรวจหาและลบที่เกิดขึ้นคำหยาบ
Utility-based agents
- มีข้อมูลบางอย่างที่อธิบายระดับของความพอใจ (เช่นเมื่อมีเงื่อนไขที่น่าพอใจหลายที่บางส่วนที่มีความสำคัญมากขึ้นกว่าคนอื่น ๆ )
Ex: แท็กซี่อัตโนมัติ - พิจารณาความถูกต้องค่าใช้จ่ายที่, เวลา, ความปลอดภัย ฯลฯ
Learning agents
- ประสบการณ์การใช้เพื่อปรับปรุงประสิทธิภาพ
Ex: แนะนำหนังสือ - สร้างรายชื่อหนังสือที่ลูกค้าอาจชอบตามเปิด / ประวัติการซื้อของเขาและเธอ
Agents
เป็นสิ่งที่รับรู้ของสภาพแวดล้อมที่ผ่านการเซ็นเซอร์และการกระทำที่ผ่านตัวกระตุ้น
เปรียบเทียบมนุษย์กับหุ่นยนต์
มนุษย์
- เซ็นเซอร์เหมือนมนุษย์ มองภาพ ได้ยินเสียง สัมผัส ได้กลิ่น รู้รส
- ตัวกระตุ้นต่อสิ่งเร้าของมนุษย์: มือขาริมฝีปากอวัยวะอื่น ๆ
หุ่นยนต์
- เซ็นเซอร์หุ่นยนต์: กล้องอินฟาเรด, ไมโครโฟน
- กระตุ้นหุ่นยนต์: มอเตอร์, ชิ้นส่วนเครื่องจักรกล
Percepts and Actions
percepts: ข้อมูลAgentจากสภาพแวดล้อม
actions: output จากAgentที่มีต่อสิ่งแวดล้อม
Rationality ความมีเหตุผล
- วัดสมรรถนะของผู้ประเมินพฤติกรรมของ agent
- rational agent ทำหน้าที่เพื่อเพิ่มค่าที่คาดหวังexpectedของการวัดประสิทธิภาพการทำงานรับ percept history ซึ่งมันต้องใช้เวลาการกระทำของมัน เชื่อว่าbelievesจะบรรลุเป้าหมาย
- เหตุผล: ทำให้ได้รับข้อมูลที่ดีที่สุด
- เหตุผล ≠ การรอบรู้ทุกอย่าง
- เหตุผล ≠ ความสำเร็จ
PEAS
การออกแบบเป็นตัวแทนที่มีเหตุผลที่เราจะต้องระบุสภาพแวดล้อมของงานซึ่งเป็นหลัก
"ปัญหา" ที่เป็น rational agents "การแก้ปัญหา"
- สี่องค์ประกอบของสภาพแวดล้อมของงาน: PEAS
- วัดสมรรถนะ
- สิ่งแวดล้อม
- Actuators
- Sensors
ตัวอย่างเช่น โปรแกรมOX
- การวัดประสิทธิภาพการทำงาน: ร้อยละที่ชนะ
- ความพึงพอใจของผู้เล่นคนที่ใช้งานง่าย
- สิ่งแวดล้อม: ผู้เล่นของมนุษย์
- Actuators: จอแสดงผลคอมพิวเตอร์อินเตอร์เฟซแบบกราฟิก
- เซนเซอร์:แป้นพิมพ์
ตัวอย่าง: แท็กซี่อัตโนมัติ
- การวัดประสิทธิภาพการทำงาน: ความปลอดภัยเวลา
- ถูกต้องตามกฎหมายกำไร ฯลฯ
- สิ่งแวดล้อม: ถนนยานพาหนะอื่น ๆ , คนเดินเท้า
- ผู้โดยสาร ฯลฯ
- Actuators: พวงมาลัยพาวเวอร์, เร่ง, เบรกสัญญาณ
- ฮอร์น, ฯลฯ
- เซนเซอร์: กล้องโซนาร์วัดความเร็ว, GPS, ฯลฯ
