Idea Transcript
Presentasi Seminar Program S3
Presentation 1
Definition : Small embedded device deployed on large scale network with capability to sense, compute, and communicate [1]
Wireless sensor combines modern sensor technology, micro electronic technology, embedded computing, communication technology, and distributed processing [1] [1] Krishnamachari Bhaskar. Mathematical Modeling and Algorithm for Wireless Sensor Network. Autonomous Network Research Group Department of Electrical Engineering-Systems USC Viterbi School of Engineering.
Challenges in Wireless Sensor Area [1] and [2]: Large scale network : monitoring scope is very wide, the number of sensor
nodes is very large, unattended ad-hoc deployment Scarce energy, low bandwidth Processing, communication and storage ability is limitted High Noise and fault rate Dynamic / uncertain environtment : dynamic topology, self-organization network, multi-hop routing Data Centric : High variation Application in application-spesific requirements
[1]
Krishnamachari Bhaskar. Mathematical Modeling and Algorithm for Wireless Sensor Network. Autonomous Network Research Group Department of Electrical Engineering-Systems USC Viterbi School of Engineering.
[2]
Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Crosslayer MAC Protocol for Wireless Sensor Networks . The IEEE Fifth International Conference on Genetic and Evolutionary Computing, 2011, IEEE.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
A large number of sensor nodes are randomly deployed in the target monitoring area, or manually deployed in a fixed position of the monitoring area, constituting a self-organize sensor network.
After sensing data, the sensor nodes firstly fuse the monitoring data, then send data to the sink node in the form of single-hop, or in the form of multi-hop through neighbor nodes, the data can be processed by many sensor nodes during transmission.
lastly the monitoring data is sent to the management node through internet or the satellite. The user configures and manages the wireless sensor network, releases monitoring task, and collect monitoring data through the management node
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
Solutions developed in research community or by groups of enthusiasts. Commercial solutions from particular producers Modules assembled by companies trying to sell software solutions
System VM virtualize hardware resources and can run directly on hardware. In embedded systems they implement functions of the OS and completely replace it Squawk, .NET Micro
Application (process) VM typically run on top of an OS as an application and support a single process. Mate, Darjeeling, VM*, SwissQM, CVM, DVM
Advantage Reduce the distribution energy costs for software updates VM code smaller than native machine code Simpler reprogramming process
Disadvantage Additional overhead Increased time and memory requirements for execution Increased energy spent in interpreting the code
has strong capability in the procession power, storage capacity and communication;
connects the sensor network and the Internet and other external networks;
achieves conversion of communication protocol between two stacks, then releases the monitoring task of management node and transmits the collected data to the external network;
can be an enhancement of sensor nodes, with sufficient energy supply and more memory, computing resource, also can be gateway devices that have the wireless communication interfaces, without monitoring function.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
can be called the user node.
is used to configure and manage the wireless sensor network, and release monitoring task and collect monitoring data.
during data transmission, sensor nodes not only can act as sensing nodes, but also can act as a router to forward data.
in recent years, the software and hardware technology of sensor node is the major issue in the research of wireless sensor networks.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
Chapter 2 Holger Karl, Andreas Willig. “Protocols And Architectures For Wireless Sensor Networks” . John Wiley & Sons Ltd. 2005
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
The sensor : monitoring the target area and data conversion.
The processor : controlling operation of sensor node, storage and procession of the data that is collected itself and from other nodes.
The wireless communication : wireless communication with other sensor nodes, exchanging control messages, sending and receiving the monitoring data. Wireless Sensor Networks typically use communication frequencies between about 433 MHz and 2.4 GHz.
The Power Unit : supplies energy for operation of sensor nodes, generally it adopts micro-batteries.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
Passive, omnidirectional sensors. These sensors can measure a physical quantity at the point of the sensor node without actually manipulating the environment by active probing – in this sense, they are passive. Moreover, some of these sensors actually are self-powered in the sense that they obtain the energy they need from the environment – energy is only needed to amplify their analog signal. There is no notion of “direction” involved in these measurements Typical examples for such sensors include thermometer, light sensors, vibration, microphones, humidity, mechanical stress or tension in materials, chemical sensors sensitive for given substances, smoke detectors, air pressure, and so on.
Passive, narrow-beam sensors These sensors are passive as well, but have a well-defined notion of direction of measurement. A typical example is a camera, which can “take measurements” in a given direction, but has to be rotated if need be.
Active sensors This last group of sensors actively probes the environment, for example, a sonar or radar sensor or some types of seismic sensors, which generate shock waves by small
Sumber : Holger Karl, Andreas Willig. “Protocols And Architectures For Wireless Sensor Networks” . John Wiley & Sons Ltd. 2005
The Processor is the core of a wireless sensor node. It collects data from the sensors, processes this data, decides when and where to send it, receives data from other sensor nodes, and decides on the actuator’s behavior.
It has to execute various programs, ranging from time-critical signal processing and communication protocols to application programs; it is the Central Processing Unit (CPU) of the node.
Such a variety of processing tasks can be performed on various controller architectures, representing trade-offs between flexibility, performance, energy efficiency, and costs.
Sumber : Holger Karl, Andreas Willig. “Protocols And Architectures For Wireless Sensor Networks” . John Wiley & Sons Ltd. 2005
The memory component is fairly straightforward. Evidently, there is a need for Random Access Memory (RAM) to store intermediate sensor readings, packets from other nodes, and so on. While RAM is fast, its main disadvantage is that it loses its content if power supply is interrupted.
Program code can be stored in Read-Only Memory (ROM) or, more typically, in Electrically Erasable Programmable Read-Only Memory (EEPROM) or flash memory (the later being similar to EEPROM but allowing data to be erased or written in blocks instead of only a byte at a time).
Flash memory can also serve as intermediate storage of data in case RAM is insufficient or when the power supply of RAM should be shut down for some time. The long read and write access delays of flash
Sumber : Holger Karl, Andreas Willig. “Protocols And Architectures For Wireless Sensor Networks” . John Wiley & Sons Ltd. 2005
Mostly performed in unlicensed bands according to open standards Standard: IEEE 802.15.4 - Low Rate WPAN ▪ 868/915 MHz bands with transfer rates of 20 and 40 kbit/s, 2450 MHz band with a rate of 250 kbit/s ▪ Technology: ZigBee, WirelessHART Standard: ISO/IEC 18000-7 (standard for active RFID) ▪ 433 MHz unlicensed spectrum with transfer rates of 200 kbit/s ▪ Technology: Dash7 Standard: IEEE 802.15.1 – High Rate WPAN ▪ 2.40 GHz bands with transfer rates of 1-24 Mbit/s ▪ Technology: Bluetooth (BT 3.0 Low Energy Mode) Standard: IEEE 802.11x – WLAN ▪ 2.4, 3.6 and 5 GHz with transfer rates 15-150 Mbit/s ▪ Technology: Wi-Fi
Sometimes in licensed bands Standard: 3GPP – WMAN, WWAN cellular communication ▪ 950 MHz, 1.8 and 2.1 GHz bands with data rate ranging from 20 Kbit/s to 7.2 Mbit/s, depending on the release ▪ Technology: GPRS, HSPA
Sometimes according to proprietary standards and protocols Z-Wave – for home automation ▪ 900 MHz band (partly overlaps with 900 MHz cellular) with data rates of 9.6 Kbit/s or 40 Kbit/s ANT – for sportsmen and outdoor activity monitoring, owned by Garmin ▪ 2.4 GHz and 1 Mbit/s data rates Wavenis – for M2M periodic low data rate communication ▪ 868 MHz, 915 MHz, 433 MHz with data rates from 4.8 Kbits/s to 100 Kbits/s ▪ most Wavenis applications communicate at 19.2 kbits/s. MiWi, SimpliciTI, Digi xxx, …
For actual communication, both a transmitter and a receiver are required in a sensor node. The essential task is to convert a bit stream coming from a microcontroller (or a sequence of bytes or frames) and convert them to and from radio waves.
For practical purposes, it is usually convenient to use a device that combines these two tasks in a single entity. Such combined devices are called transceivers. Transmitter State : • Transmit : the transmit part of the transceiver is active and the antenna radiates energy.
Sumber : Holger Karl, Andreas Willig. “Protocols And Architectures For Wireless Sensor Networks” . John Wiley & Sons Ltd. 2005
•
Receive : receive part is active.
•
Idle : A transceiver that is ready to receive but is not currently receiving. Many parts of the receive circuitry are active, and others can be switched off. For example, in the synchronization circuitry, some elements concerned with acquisition are active, while those concerned with tracking can be switched off and activated only when the acquisition has found something.
•
Sleep : significant parts of the transceiver are switched off.
For wireless sensor nodes, the power supply is a crucial system component. There are essentially two aspects: storing energy and providing power in the required form attempting to replenish consumed energy by “scavenging” it from some node-external power source over time.
Storing power is conventionally done using batteries. As a rough orientation, a normal AA battery stores about 2.2–2.5Ah at 1.5 V. Energy scavenging has attracted a lot of attention in research. Sumber : Holger Karl, Andreas Willig. “Protocols And Architectures For Wireless Sensor Networks” . John Wiley & Sons Ltd. 2005
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
The physical layer provides a interface between data link layer and physics wireless signal path with radio frequency firmware and hardware.
The physical layer is the bottom layer, charging with the task of directly action with the outside.
Meanwhile, the physical layer offers physical layer data service and physical layer management service, also maintains the information base of physical layer.
The major tasks of the physical layer:
Open and close wireless transceiver; Energy detection; Link quality indication; Clear channel assessment; Channel selection; Data transmission and data reception.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
The MAC layer offers MAC layer data service and MAC layer management service. The MAC layer data service guarantees right sending and receiving
data of MAC protocol data unit in physical layer data service. The MAC layer data service maintains the database that stores the relevant information of MAC sub layer protocol state.
In IEEE802.15.4 criterion, the major tasks of the MAC sub layer :
Coordinator generates network beacons; Beacon synchronization; Support PAN relevance and solution relevance; Support equipment safety; CSMA-CA channel access mechanism; Process and maintain guaranteed time slot mechanism; Support reliable link between two equal MAC entities.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
The main function of network layer is providing some necessary functions, ensure compatible with IEEE 802.15.4 criterion, meanwhile supply suitable function interfaces for application layer.
The major tasks of network layer : Produce package of internet layer; Routing of the network topology; Configure new device parameters; Establish the PAN network; Access or break PAN network; Allocate network address; Discover and maintain the network neighbor information; Supply routing, control the reception time and state of the receptor.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
The Application layer includes a series of application layer software based on monitoring tasks.
Similar to transmission layer, the research of application layer is relatively less. The potential problems of sensor network application layer to be resolve are sensor management protocol, task allocation, data broadcast management protocol and sensor query.
Application support services of sensor network : time synchronization : provides sensor nodes working with local timepiece synchronization; the node location service depends on limited known nodes to locate positions of other nodes, establishing definite space relation in the system.
Sumber : Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . 2011 Fifth International Conference on Genetic and Evolutionary Computing. IEEE.
Chapter 1 Application of Industrial Wireless Sensor Networks Book of Industrial Wireless Sensor Networks Applications, Protocols, and Standards CRC Press . Edition 2013 Milan Erdelj, Nathalie Mitton, Enrico Natalizio FUN Research Group, INRIA Lille - Nord Europe, France
Operate autonomously IWSN should not represent additional burden for human. It is easy
to deploy, configure, when deployment site is inaccessible for human (Maintaiability)
Reliability Provide accurate and real time information regarding monitored
process even in harsh industrial environments under extreme vibration, noise, humadity, and temperature condition.
System Security The information gathered during the monitoring process is vital for
proper system operation, given that even the smallest error can produce fatal consequrnces for both system and product.
Propagation Environment The designer has to deal with interferrence and the radio environment
produced by production machine. If the sensor is deployed at outdoor, the radio propagation can be assimilated to a free-range perturbation.
Operation Life Time The power management policy : Selecting The proper Components
(Hardware point of view) and Controlling Sending and Receiving message (Software point of view)
Heterogenity Heterogenity of data collected : Proper data fusion/aggregation schemes,
Powerful technique of data analysis for the reception side Heterogenity of objective network : Focus on logistic application where the IWSN used to monitor the transportation of some good must be able to integrate with the IWSN deployed both production site and delivery site.
Enviromental Sensing Problem of air, water, pollution, fire, flood, landside
Condition Monitoring Health information (building, construction, bridges, supply
route, etc), Machine condition (factory automation), health care information
Process Automation Resource of production and service provision including
material, stock, supply chain status. The most important issue from human perpective is the production performance monitoring, evaluation, and improvement
General objective in the environmental monitoring is an efficient information gathering, used both for prevention (real-time or postponed) and analysis.
The importance of the pollution detection both in materials for production as well as in the production ambients make the pollution monitoring one of the most widely spread field of application in enviromental sensing.
Some related research : A Low cost, Fully automated, end-to-end in sewer gas monitoring
system based on floatting-drifting embedded sensor platform Some technique to allow web users to access high-resolution polution data gathered from large number of vehicle-mounted mobile sensing devices coupled with highly-accurate static sensor data in an easy-to-use, intuitive interface. Prototype of a platform for collection and logging of the outdoor noise pollution measurements. These measurements can be used for analysis of pollution effect on manpower productivity and social behaviour.
Industrial facilities are often localized in environments taht are riskier than residentalo areas, especially in the case of oil, gas, coal mining industries, or agricultural companies. Therefore, proper early warnings or predictive disaster detection might be a valuable asset, resource, and life saver.
Some related research : River Flood detection. A sensor network is used for
flood prediction based on the previous measurements. By Using a small number of sensor nodes with self-monitoring for failure capabilities, they cover and secure large geographical area under the threat of disaster the debris flow monitoring system that allows in-situ real-time debris flow tracking. A number of robust sensors with self-localization capabilities are thrown into the flow, thus providing the real time flow direction and volume information used for early warning issuing.
The security refers to the security of the information and the security of the people, products and equipment
Some related research : a fence surveillance system that comprises the robot
and camera sensor network and two types of nodes, ground and fence nodes. The network reports the acquired data to the base station with issues commands to mobile robots that extend the communication distance of the system.
Objective : a need for structural and equipment monitoring techniques that could provide global picture on subject condition and accurately predict equipment failures and therefore improve component and equipment reliability and performance. Furthermore, structural monitoring system detects system damages before possible failures and minimizes the time that production line spends out of service, and thus increases the profit.
Wireless sensor networks are well suited for the structural health monitoring since they are easily deployable and configurable for this purpose.
Related Research : a wireless data acquisition system that is
used for damage detection on the building. wireless sensor network on two wind turbines in order to gather the vibrational output data and to provide better models of wind turbine dynamic behavior and response. requirement, challenges, their design and implementation of WSN for health monitoring of Golden Gate Bridge in San Francisco Bay, USA.
The production process speed and quality depends on the equipment condition and accuracy.
Related Research : Developing the wireless network system for a team of
underwater collaborative autonomous agents that are capable of locating and repairing scale formations in tanks and pipes within inaccessible environments WSN whose aim is to detect, localize and quantify bursts, leaks and other anomalies (blockages or malfunctioning control valves) in water transmission pipelines.
Process monitoring focuses on tracking the quality of the entire life of a product, step by step from the materials provision used for its production till its disposal. The role of IWSNs in these applications is driven by the need for
evaluating and improving each and every step of goods productiondistribution-consumption process as well as the cycle as a whole.
Service monitoring is mainly related to evaluating the quality of the provision of a specific service to end-users. From providers' perspective, remote monitoring/metering of
electricity power, heat, water or gas. From consumer's perspective, IWSNs' applications represent a remarkable step in the direction of the green building deployment because they allow end-users to constantly estimate their energy expenditure as well as the quality of the environment where they live.
easy-to-install self-calibrating system that provides users with information on when, where, and how much water they are using. The approach is non-intrusive, cost-effective and easy to deploy. It is based on wireless vibration sensors attached to pipes, which are able to measure the water flow passing through the pipe and estimate consumption.
a system for AC energy monitoring in large and diverse building environments. Their system provides real, reactive and apparent power measurements and comprises the metering control interface, IP compatible network structure and software that provides various power centric applications.
a way to apply the dynamic WSN in temperature controlled supply chain (cold chain) for fruit and pharmaceutical product storage and transport to avoid degradation and spoilage.
The design, development and deployment of a WSN that
improves the water efficiency in the field irrigation located in dry regions. In this way, with the use of temperature and humidity information it is possible to implement the automated control system that consume irrigation water in efficient manner
The architecture, hardware and the software of the platform used for precision viticulture. A major feature of this platform is its power-management subsystem, able to recharge batteries with energy harvested from the surrounding environment.
a novel control architecture that uses occupancy sensing to guide the operation of a building heating ventilation and airconditioning systems. By interacting between sensing and actuating part of the HVAC control, they achieve significant results in energy saving
Many researchers pay more attention to : optimization between MAC layer and other layers of network stack from the standpoint of cross-layer design. For example, interaction between physical layer and MAC layer,
combination of MAC protocol and routing, so as to increase efficiency of MAC protocol, realize lightweight protocol and reduce the cost.
Now cross-layer optimization is one of the key issues in research on the MAC protocol for WSN.
The research of application layer is relatively less. The potential problems of sensor network application layer to
be resolve are sensor management protocol, task allocation, data broadcast management protocol and sensor query.
Lizhong Jin, Jie Jia, Dong Chen, Fengyun Li, Zhicao Dong, Xue Feng. Research on Architecture, Cross-layer MAC Protocol for Wireless Sensor Networks . The IEEE Fifth International Conference on Genetic and Evolutionary Computing, 2011, IEEE.
experimental studies of wireless link quality a fundamental theorem concerning random
geometric graphs analysis of routing with compression linear/non-linear flow optimization formulations of WSN routing best radio signal strength-based localization technique to date new querying and search techniques for WSN algorithms for low latency scheduling and routing
Krishnamachari Bhaskar. Mathematical Modeling and Algorithm for Wireless Sensor Network. Autonomous Network Research Group Department of Electrical Engineering-Systems USC Viterbi School of Engineering.
Presentation 2
NETWORK ARCHITECTURE
PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS Holger Karl University of Paderborn, GERMANY Andreas Willig Hasso-Plattner-Institute at the University of Potsdam, GERMANY
Presentation Title 1 Introduction to Wireless Sensor Networks and Applications 2 Network Architecture 3 Seminar : Mobile Agent Platfform for WSN 4 Mobile Agent : Mobility and Communication 5 Mobile Agent : Coordination 6 Data Centic and Content-based Protocol 7 Data Mining and Information Retrieval
Disadvantage : limitation on the feasible distance between a sender and a receiver. limited distance, the simple, direct communication between source and sink is not always possible, specifically in WSNs, which are intended to cover a lot of ground (e.g. in environmental or agriculture applications) or that operate in difficult radio environments with strong attenuation (e.g. In buildings).
The concept of multihop networks is particularly attractive for WSNs as the sensor nodes themselves can act as such relay nodes, foregoing the need for additional equipment. Depending on the particular application, the likelihood of having an intermediate sensor node at the right place can actually be quite high – for example, when a given area has to be uniformly equipped with sensor nodes – but nevertheless, there is not always a guarantee that such multihop routes from source to sink exist, nor that such a route is particularly short.
The scenario in the lower half, both sinks and active sources are used to forward data to the sinks at the left and right end of the network
Node Mobility Sink Mobility Event Mobility
Node Mobility The wireless sensor nodes themselves can be mobile. The meaning of such mobility is highly application dependent. In examples like environmental control, node mobility should not happen; in livestock surveillance (sensor nodes attached to cattle, for example)
Sink mobility. While this can be a special case of node mobility, the important aspect is the mobility of an information sink that is not part of the sensor network, for example, a human user requested information via a PDA while walking in an intelligent building.
Event mobility In applications like event detection and in particular in tracking applications, the cause of the events or the objects to be tracked can be mobile. In such scenarios, it is (usually) important that the observed event is covered by a sufficient number of sensors at all time. Hence, sensors will wake up around the object, engaged in higher activity to observe the present object, and then go back to sleep.
Quality of Service Energy Efficiency Scalability Robustness
Event detection/reporting probability. probabilitas di mana event yang muncul tidak terdeteksi atau tidak dilaporkan ke sink ?
Event Classification Error. Event tidak hanya dideteksi, tetapi juga harus diklasifikasi
Event Detection Delay. Berapa delay yang terjadi antara mendeteksi event dan melaporkannya ke sink
Missing Report Aplikas yang membutuhkan laporan secara periodik, probabilitas laporan yang tidak
terkirim harus kecil
Approximation Accuracy Untuk fungsi aplikasi aproksimasi, berapa rata-rata/nilai error maksimum absolut atau
relatif terhadap nilai aktual
Tracking accuracy Aplikasi tracking tidak boleh kehilangan obyek yang sedang di-track. Posisi yang
dilaporkan harus semirip mungkin dengan posisi real-nya. Hal ini erkait dengan sensitifitas sensor.
Energy per correctly received bit Berapa rata-rata energi yang dikonsumsi untuk mengirim satu bit informasi (payload)
dari sumber ke tujuan.
Energy per Reported (Unique) Event Berapa rata-rata energi yang dikonsumsi untuk mengirimkan laporan event yang unik.
Karena event yang sama dilaporkan dari berbagai sumber, perlu dilakukan normalisasi pengukuran ke hanya satu event yang unik (informasi redundant tentang event yang sudah terdeteksitidak akan memberikan informasi tambahan)
Delay/Energy Trade-Off Ada beberapa aplikasi yang difungsikan untuk mendeteksi “urgent” events, di mana
dapat dijustifikasi adanya investasi energi yang meningkat untuk melaporkan event itu secara cepat. Di sini adanya trad-off antara delay dengan overhead energi
Network Lifetime Time to first node death. Kapan energi node pertama di jaringan kehabisan energi dan berhenti beroperasi Network half-life . Kapan 50% dari total node kehabisan energi dan berhenti beroperasi. Time to partition. Kapan partisi jaringan pertama tidak terhubung. Time to loss of coverage. Kapan pertama kali area spot tidak dapat lagi di-cover olehsensor yang terpasang di dalamnya.
Skalabilitas : Kemampuan untuk memelihara karakteristik-karakteristik kinerja sebuah jaringan WSN
Robustness : WSN tidak boleh fail hanya karena jumlah node yang tertentu kehabisan energi, atau karena lingkungan berubah sehingga memutuskan jalur radio antar dua node. Kegagalan ini harus dikompensasi dengan menemukan jalur alternatif lainnya.
Untuk optimisasi skalabilitas dan robustness biasanya diimplementasikan arsitektur terdistribusi. Hal ini berarti bahwa tidak adanya satu entitas yang memiliki tugas yang tersentarlisasi seperti mengontrol medium access ataumembuat routing decision, sebagaimana halnya dilakukan base station di dalam jaringan seluler. Kelemahan dari pendekatan tersentralisasi ini adalah keterbatasan rentang komunikasi.
Node-node WSN seharusnya secara kooperatif mengorganize jaringan menggunakan algoritma dan protokol terdistribusi. Inilah dikenal dengan istilah Self-organization.
Ketika mengorganisir jaringan terdistribusi, perlu diperhatikan kelemahan pendekataan ini. Untuk beberapa keadaan, pendekatan tersentralisasi dapat memberikan solusi khususnya terkait dengan efisiensi sumber daya, misalnya energi. Untuk itu perlu adanya kombinasi, yaitu penggunaan prisip sentralisasi dengan memilih node spesifik sebagai agent yang tersentralisasi, sebagai contoh untuk menorganisir medium access. Pemilihan node ini menghasilkan hirarki yang dinamik – Lebih ditail dijelaskan di presentasi tentang “Topology Control”
Ketika mengorganisir WSN yang terdistribusi, node tidak hanya mengirim paket atau mengeksekusi program aplikasi saja,tetapi node juga aktif terlibat dalam penentuan keputusan tentang cara mengoperasikan jaringan. Inilah yang dikenal sebagai bentuk spesifik permosesan informasi yang terjadi di dalam jaringan. Konsep ini dikenal dengan in-network processing . Lebih ditail dijelaskan di presentasi tentang “Data Centric and ContentBased Networking”
Teknik-tekinik terkait in-Network Processing Aggregation Distributed source coding and distributed compressing Distributed and Collaborative Signal Processing Mobile Code/Agent-based signal Processing
Teknik pemrosesan yang paling sederhana dalam jaringan adalah aggregation. Jika misalkan sink memperoleh hasil pengukuran periodik dari semua sensor, namun hanya relevan untuk mengecek nilai rata-rata telah berubah atau perbedaan antara nilai minimum dan maksimum cukup besar. Pada kasus ini, sebaiknya tidak mengirim semua data yang dibaca oleh semua sensor ke sink, namun lebih efisien untuk mengirim data rata-rata atau nilain maksimum dan minimum saja.
Pengiriman data mengkonsumsi lebih banyakenergi daripada melakukan komputasi komplek
Aggregation mengurangi atau mengorbankan informasi tentang besaran pengukuran untuk dapat mentransmisikan semua bita data dari semua sumber ke sink. Apakah mungkin mengurangi jumlah bit yang ditransmisika, namun masih mendapatkan informasi penuh tentang semua sensor ?
Permasalahan ini terkait dengan masalah di coding dan kompresi yang saat ini dikenal dalam jaringan biasa di mana sebagian besar usaha diinvestasikan dalam proses encode. Pada kasus WSN, proses encode ini menyebabkan komputasi terlalu komplek untuk sensor node.
Bagaimana informasi yang dihasilkan oleh multiple sensor dimanfaatkan untuk membantu dalam coding ? Beberapa informasi joint antar dua sensor diperlukan. Pembacaan sensor-sensor yang berdekatan biasanya akan sama sehingga keduanya bisa saling berkorelasi. Korelasi ini dapat digunakan tidak hanya menyederhanakan jumlah data yang ditrasnmisikan, namun juga menyimpan overheadnya di sensor node.
Ketika komputasi komplek dari beberapa jumlah data harus dilakukan di WSN, masih ada efisiensi energi untuk melakukan komputasi ini jika jumlah return data yang ditransmisikan dapat dikurangi.
Contoh untuk konsep ini adalah komputasi terdistribusi Fast Fourier Transform (FFT). Bergantung kepada dimana lokasi data diinput, ada beberapa algoritma yang tersdia untuk menghitung FFT secara terdistribusi di mana di dalamnya ada trade-off antara kompleksitas komputasi secara lokal dan keperluan komunikasi. Namun, yang perlu dipertimbangkan adalah pada pemilihan algoritma yang mempertimbangkan : Latency komunikasi Konsumsi energi untuk berkomunikasi Proses komputasi
Ide dari mobile code/agent-based networking adalah kode program yang cukup kecil yang bisa dikirim dari satu node ke node lain. Kode ini selanjutnya dieksekusi secara lokal, lalu diputuskan ke mana kode ini dikirim selanjutnya.
Sebagai contoh, software agent yang dikirim untuk mengumpulkan kemungkinan terbaik dari rute perjalanan dari satu tempat ke tempat lainnya. Salah satu contoh pendekatan biologi yang menginspirasi
algoritma untuk aplikasi di atas adalah genetic algorithm, swarm intelligence.
Pada jaringan komunikasi biasa, fokus hubungan komunikasi terletak pada pasangan komunikasi antar peer, pengirim dan penerima data.
Pada WSN, fokus utama bukan pada identitas sensor node, tetapi pada informasi aktual yang dilaporkan terkait dengan lingkungan fisik
Jadi fokus perhatian bukan pada identitas node, tetapi pada data dinamakan data-centric networking.
Pada Aplikasi Data-centric, semua yang aplikasi harus lakukan adalah me-state dirinya untuk diberi informasi tentang event. Node-node di dalam network yang mendeteksi event tertentu secara implisit diberitahu tentang request ini.
Pada identity-centric network, node yang me-request mencari semua node yang menyediakan kapabilitas dan memanggilnya secara eksplisit. Sebagai contoh , pertimbangkan lokasi node sebagai properti yang mendefinsikan apakah node berada dalam grup tertentu atau bukan. Pada contoh ini, ada keinginan untuk berkomunikasi dengan semua node di area yang ditentukan untuk memperoleh rata-rata suhu yang diukur oleh semua node di area tertentu
There are some evident similarities between well-known peer-to-peer applications like file sharing and WSN: In both cases, the user/requester is interested only in looking up
and obtaining data, not in its source; the request for data and its availability can be decoupled in time; both types of networks should scale to large numbers.
In peer-to-peer networking, the solution for an efficient lookup of retrieval of data from an unknown source is usually to form an overlay network, implementing a Distributed Hash Table. The desired data can be identified via a given key (a hash) and the DHT will provide one (or possibly several) sources for the data associated with this key.
The required separation in both time and identity of a sink node asking for information and the act of providing this information is not well matched with the synchronous characteristics of a request/reply protocol.
This behavior is realized by the publish/subscribe approach : Any node interested in a given kind of data can subscribe to it, and any node can
publish data, along with information about its kind as well. Upon a publication, all subscribers to this kind of data are notified of the new data. The elephant example is then easily expressed by sink nodes subscribing to the event “elephant detected”; any node that is detecting an elephant can then, at any later time, publish this event. If a subscriber is no longer interested, it can simply unsubscribe from any kind of event and will no longer be notified of such events. Evidently, subscription and publication can happen at different points in time and the identities of subscribers and publishers do not have to be known to each other.
Publish/subscribe networking is a very popular approach for WSN. In fact, some of the most popular protocols are incarnations of this principle and are discussed in detail in separated presentation “Data-centric and contentbased networking “
A somewhat different view on WSN is to consider them as (dynamic) databases. This view matches very well with the idea of using a data-centric organization of the networking. protocols. Being interested in certain aspects of the physical environment that is surveyed by a WSN is equivalent to formulating queries for a database.
To cast the sensor networks into the framework of relational databases, it is useful to regard the sensors as a virtual table to which relational operators can be applied. Then, extracting the average temperature reading from all sensors in a given room can be simply written :
Exploit Location Information Exploit Heterogenity Component-based Protocol Stack and Cross Layer Optimization Adaptive Fidelity and Accuracy
There is the design choice between treating the application as just another component or designing a service interface that makes all components, in their entirety, accessible in a standardized fashion. A service interface would allow to raise the level of abstraction with which an application can interact with the WSN . Such a service interface can hide considerable complexity and is actually conceivable as a “middleware” in its own right.
Support for Simple request/response
Support for asynchronous event notification
Addresses should be definable in several way
For both types of interactions, the addressees should be definable in several ways. The simplest option is an explicit enumeration of the single or multiple
communication peers to whom a (synchronous or asynchronous) request is made
In-networking processing functionality has to be accessible. For an operation that accesses an entire group of nodes, especially when reading
values from this group (either synchronously or asynchronously), it should be possible to specify what kind of in-network processing should be applied to it. In addition, it can be desirable for an application to be able to infuse its own innetwork processing functions into the network. For example, a new aggregation function could be defined or a specific mobile agent has to be written by the application programmer anyway.
The specification of the required accuracy of a result. This can take on the form of specifying bounds on the number of group members that should contribute to a result, or the level of compression that should be applied -> acceptable energy expenditure
Timeliness requirements about the delivery of data is a similar aspect. possible to provide a result quickly but at higher energy costs (e.g. by forcing nodes to wake up earlier than they would wake up anyway) or slowly but at reduced energy costs (e.g. By piggy-backing information on other data packets that have to be exchanged anyway).
The need to access location, timing, or network status information (e.g. energy reserves available in the nodes or the current rate of energy scavenging) via the service interface.
The need for an explicit description of the set of available capabilities of the node/the network – for example, which physical parameters can be observed or which entities can be controlled
Security Requirement
While not a direct part of an actual service interface, additional management functionality, for example, for updating components, can be convenient to be present in the interface as well
For practical deployment, a sensor network only concerned with itself is insufficient. The network rather has to be able to interact with other information devices, for example, a user equipped with a PDA moving in the coverage area of the network or with a remote user, trying to interact with the sensor network via the Internet .
For example, a sensor node wants to deliver an alarm message to some Internet host. The first problem to solve is akin to ad hoc networks, namely, :
how to find the gateway from within the network. ? – Integrating routing and service discovery If several such gateways are available, how to choose between them? How to handle several gateways, each capable of IP networking, and the communication among them? - One option is to build an IP overlay network on top of the sensor how does a sensor node know to which Internet host to address such a message? Or even worse, how to map a semantic notion (“Alert Alice”) to a concrete IP address? Even if the sensor node does not need to be able to process the IP protocol, it has to include sufficient information (IP address and port number, for example) in its own packets; the gateway then has to extract this information and translate it into IP packets. An ensuing question is which source address to use here .
The gateway in a sense has to perform tasks similar to that of a Network Address Translation (NAT)
How Internet-based entity trying to access services of a WSN ?
The more general case is, however, a terminal “far away” requesting the service, not immediately able to communicate with any sensor node and thus requiring the assistance of a gateway node. How to find out that there actually is a sensor network in the desired
location ? and how to find out about the existence of a gateway node?
Once the requesting terminal has obtained this information, how to access the actual services?
The requesting terminal can instead send a properly formatted request to this gateway, which acts as an application-level gateway or a proxy for the individual/set of sensor nodes that can answer this request;
The gateway translates this request into the proper intrasensor network protocol interactions. This assumes:
that there is an application-level protocol that a remote requester and gateway can use; that is more suitable for communication over the Internet than the actual sensor network protocols; and that is more convenient for the remote terminal to use.
The gateway can then mask, for example, a data-centric data exchange within the network behind an identity-centric exchange used in the Internet.
There are some clear parallels for such an application-level protocol with so-called Web Service Protocols, which can explicitly describe services and the way they can be accessed.
The Web Service Description Language (WSDL) [166], in particular, can be a promising starting point for extension with the required attributes for WSN service access – for example, required accuracy, energy trade-offs, or data-centric service descriptions. Moreover, the question arises as to :
how to integrate WSN with general middleware architectures [699] or how to make WSN services accessible From a standard Web browser (which should be an almost automatic by-product of using WSDL and related standards in the gateway). However, research here is still in its early infancy [384, 508, 656].
WSDL
The gateways can also act as simple extensions of one WSN to another WSN. The idea is to build a larger, “virtual” WSN out of separate parts, transparently “tunneling” all protocol messages between these two networks and simply using the Internet as a transport network.
Seminar Presentation
Stefano Galzarano , Francesco Aielo, Alesio Carbone, Giancarlo Fortino. JavaBased Mobile Agent Platform for Wireless Network Sensor. the International Multiconference on Computer Science and Information Technology pp. 165– 172. 2010
Agent adalah sistem komputer yang mempunyai kemampuan untuk melakukan aksi otonom untuk mencapai obyektif yang diinginkan penggunanya.
Sistem Multiagent adalah sistem yang terdiri dari agent-agent yang berinteraski satu sama lain untuk melakukan kerja sama, koordinasi, dan negosiasi.
close-coupled, yaitu interaksi yang terus menerus dengan lingkungannya Sense-decide-act-sense-decide
Tiga perilaku intelligent agent : Reactive, yaitu sistem memelihara interaksi yang sedang berjalan
dengan lingkungannya dan memberikan respon terhadap perubahan yang terjadi.
Pro-Active (goal directed behaviour.) yang berarti menghasilkan dan
berusaha untuk mencapai goal, tidak hanya didorong oleh event, namun punya inisiatif dan mengenali opportunity
Social , yaitu kemampuan untuk berinteraksi dengan agent-agent lainnya
(dan juga mungkin manusia) melalui beberapa jenis komunikasi agent dan juga bekerja sama dengan agent-agent lainnya.
Obyek : enkapsulasi beberapa state komunikasi melalui pengiriman pesan memiliki method terkait dengan operasi yang dapat dilakukan
pada state-nya
Agent otonom : memasukkan notasi otonom yang lebih kuat dari obyek.
Agent memutuskan sendiri apakah perlu atau tidak melakukan aksi yang diminta agent lainnya agent harus cerdas : punya kapabilitas fleksibel (reactive- pro active- social) agent adalah aktif : bukan provider layanan yang pasif. entitas yang perilakunya dapat diprediksi dengan mengatributkan belief, desires, dan kecerdasan rasional
Mobile Agent (MA) adalah entitas piranti lunak yang me-enkapsulasi perilaku dinamis dan punya kemampuan untuk bermigrasi dari satu node komputasi ke node lainnya untuk menyelesaikan tugas-tugas terdistribusi.
MA dapat mendukung pemrograman WSN pada tingkat aplikasi, middleware, dan network.
Mengapa menggunakan MA untuk sistem terdistribusi :
Mengurangi beban jaringan Mengurangi Network Latency Enkapsulasi Protokol Eksekusi asinkron dan otonom Adaptasi yang Dinamis Orientation to Heterogenity Kehandalan dan Toleransi Kesalahan
MA didukung oleh Mobile Agent System (MAS) yang menyediakan : API untuk mengembangkan aplikasi berbasis agent Agent server yang mengeksekusi agent-agent dengan menyediakan
layanan dasar seperti migrasi, komunikasi, dan pengaksesan sumber daya node.
Contoh MA : Agilla, ActorNet, MAPS, dan AFME
Agilla adalah middleware berbasis agent yang dikembangkan di atas TinyOS dan mendukung multipe agent pada setiap nodenya.
Agilla menyediakan dua sumber daya fundamental pada setiap nodenya : Tuplespace merepresentasikan ruang memory yang di-share di mana
data terstruktur (tuple) disimpan dan diambil, memungkinkan agent bertukar informasi secara decouple. Tuplespace dapat diakses secara remote. Neighbour List mendaftarkan alamat-alamat node tetangga dalam satu hop. Neighbour List diperlukan jika ebuah agent harus bermigrasi
Agent-agent dapat bermigrasi membawa kode dan state-nya, namun tidak membawa tuple-nya yang disimpan di tuplespace.
Paket-paket yang digunakan untuk komunikasi node sangat kecil untuk meminimalisir message loss daripada menggunakan teknik transmisi ulang.
ActorNet adalah platform berbasis agent yang secara spesifik dirancang untuk node sensor berbasis Mica2/TinyOS.
Untuk menangani kesulitan pada migrasi kode dan interoperabilitas yang disebabkan oleh coupling yang ketat antara aplikasi dengan arsitekturarsitektur node sensor, ActorNet menerbitkan service seperti virtual memory, context switching, dan multitasking. Fitur ini efektif mendukung pemrograman agent dengan
menyediakan lingkungan komputasi yang seragam untuk semua agent, tanpa memperhatikan perbedaan piranti lunak dan piranti keras.
MAPS merupakan framework inovasi berbasis Java yang dikembangkan di atas teknologi Sun Spot untuk memfasilitasi pemrograman berorientasi agent di aplikasi WSN.
MAPS dirancang berdasarkan kebutuhan : Component-based lightweight agent server architecture untuk
mencegah model kerja sama dan concurency yang berat Lightweight agent architecture untuk mengeksekusi dan memigrasi agent secara efisien Core service yang minimal seperti migrasi agent, penamaan agent, komunikasi agent, pengaksesan sumber daya sensor dan node (sensor, actuator, flash memory, dan radio) Plug-in based architecture extension Bahasa Java untuk mendefinisikan perilaku mobile agent.
Mobile Agent (MA) merupakan komponen tingkat tinggi yang didefinisikan pengguna untuk menjalankan aplikasi berbasis agent;
Mobile Agent Execution Engine (MAEE) mengelola eksekusi MA. MAEE mengimplementasikan event-based scheduler yang memungkinkan concurrency ringan;
Mobile Agent Migration Manager (MAMM) merupakan komponen yang mengelola migrasi agent;
Mobile Agent Communication Channel (MACC) mengelola komunikasi antar agent berbasis pesan asinkron yang didukung protokol radiogram;
Mobile Agent Naming (MAN) merupakan komponen yang mengelola penamaan agent berbasis proxy. MAN juga mengelola daftar dinamis dari node sensor tetangganya.
Timer Service (TS) mengelola layanan timer untuk mendukung operasi MA.
Resource Manager (RM) mengatur akses ke sumber daya Sun SPOT node seperti sensor ( accelerometer, temperature, cahaya), switch, battery, led, dan flash memory.
Perilaku dinamis MA dimodelkan dengan multi-plane state machine (MPSM). Setiap plane dapat merepresentasikan perilaku MA pada peran yang spesifik sehingga memungkinkan pemrograman berbasis peran (role-based programming)
Plane disusun oleh variabel-variabel lokal, fungsi-fungsi lokal, dan automaton yang transisinya diberi label dengan aturan Event-Condition-Action (ECA), atau ditulis E[C]/A
Dimana E adalah nama event, [C] adalah ekspresi boolean berbasis pada lokal dan global variable, dan A adalah aksi atomik.
Pemrograman agent berbasis MPSM menerapkan tiga pradigma untuk pemrograman WSN : Pemrograman event-driven Pemrograman berbasis state Pemrograman berbasis mobile agent
AFME merupakan platform agent yang merujuk pada J2ME MIDP ringan open source dan menerapkan Agent Factory Framework yang ada.
AFME ditujukan untuk sistem wireless pervasive sehingga secara spesifik AFME tidak dirancang untuk WSN. Namun, karena dukungan J2ME kepada platform sensor Sun Spot, AFME dapat diadopsi untuk pengembangan aplikasi WSN berbasis agent.
AFME berbasis pada pradigma Believe-Desire-Intention di mana di dalamnya agent-agent mengikuti siklus sensedeliberate-act
Komponen-komponen sistem yang dapat digunakan pengembang dalam membangun aplikasi : Perceptor dan Actuator memungkinkan agent untuk melakukan
pengindraan dan melakukan aksi terhadap lingkungannya Module merepresentasikan ruang informasi yang di-share antara actuator dengan perceptor pada agent yang sama dan digunakan ketika perceptor merasakan dampak resultan dari actuator yang mempengaruhi internal state instance agent. Service merupakan ruang informasi yang di-share antara agentagent dan digunakan untuk pertukaran data antar agent.
Agent secara periodik dieksekusi menggunakan scheduler dan 4 fungsi dilakukan.
Ketika perceptor diaktifkan, operasi pengindraan menghasilkan belief yang selanjutnya ditambahkan ke belief setnya agent. Belief adalah representasi simbolik informasi terkait dengan state
agent atau kondisi lingkungan
Agent Desire diidentifikasi menggunakan reasoning berbasis resolusi Mekanisme queri berbasis goal umumnya diterapkan dalam intrepeter
prolog.
Agent Commitment (Subset Desire) diidentifikasi
Bergantung pada commitment yang diadopsi, beberapa actuator diaktifkan.
Agent didefinisikan melalui mixed declarative/imperative programming model bernama Agent Factory Agent Programming Language (AFAPL), berbasis formalisme logik belief dan commitment
AFAPL digunakan untuk me-encode perilaku agent dengan menentukan aturan-aturan yang mendefinisikan kondisi-kondisi dimana commitment diadopsi. Rule deklaratif diekspresikan dalam bentuk : b1, b2, ..., bn > doX di mana b1.. bn merepresentasikan belief dan doX adalah aksi.
Kode Java digunakan untuk me-encode perceptor dan actuator.
Waktu komunikasi agent dihitung untuk dua agnet yang berjalan di node berbeda. Keduanya berkomunikasi seperti client/server. Skema request/reply digunakan : Data Back and Forward (B&F). Request dan reply terdiri dari
data dengan besar yang sama Data B. Hanya reply saja yang memiliki data.
Waktu Migrasi agent dihitung untuk skenario ping pong antara dua sensor node (single hop). Data yang dikirim dibuat variatif
Waktu migrasi cukup besar disebabkan oleh lambatnya operasi SquawkVM untuk proses migrasi.
MAPS v.s AFME
MAPS AND AFME
One of the most poplar technologies in the WSN area is Sun SPOT (Small Programmable Object Technology). It contains 32-bit ARM9 CPU, 512K memory, 2 Mb flash storage and wireless networking is based on ChipCon CC2420 following the 802.15.4 standard with integrated antenna and operates in the 2.4GHz to 2.4835GHz ISM unlicensed bands. The IC contains a 2.4GHz RF transmitter/receiver with digital direct sequence spread spectrum (DSSS) baseband modem with MAC support.
Sumber : Magyar Kutatók 10. Nemzetközi Szimpóziuma 10th International Symposium of Hungarian Researchers on Computational Intelligence and Informatics
Dua node sensor dengan tiga agent yang berinteraksi : DataCollectorAgent mengumpulkan data
terkait dengan sensor node Sun Spot (accelerometer, temperatur, dan cahaya)
DataMessangerAgent membawa data
pengindraan yang dikumpulkan ke basestation
DataViewerAgent menampilkan koleksi data yang
diterima.
Perceptor. AccPerc, LightPerc, dan TempPerc digunakan untuk
memperoleh data dari sensor SunSPOT.
VerifyNumDataSamplePerc diperlukan untuk menentukan
apakah semua data sensor telah terkumpul untuk dilakukan komputasi.
VerifyFeaturesComputedPerc mengecek apakah semua
fitur (min, max, mean) telah dikomputasi.
TimerPerc mengecek apakah waktu sudah kadaluarsa SwitchPressedPerc mengenali user menekan tombol switch.
Actuator. TimerActivatorAct dan ResetTimerAct digunakan untuk mengaktifasi/mereset timer di node sensor. ResetAccValueAct, RegisterLightValueAct, dan
RegisterTempValueAct digunakan untuk menyimpan data yang di-sense ke dalam ShareDataModule untuk di-share dengan perceptor.
Aktuator DeactAccSensorAct, DeactLightSensorAct, dan
DeactTempSensorAct akan diaktifkan setelah sensor membaca dan digunakan untuk mencegah perceptor sensor untuk membaca data sensor berkali-kali sebelum waktu kadaluarsa timer.
Aktuator ActivateSensorAct digunakan untuk meakukan re-enable sensor
membaca setelah waktu kadaluarsa.
Aktuator ComputeFeatureAct digunakan untuk melakukan komputasi fitur data
sensor yang terkumpul
Aktuator ResetValuesAct digunakan untuk melakukan re-inisialisasi semua struktur
data setelah menyelesaikan komputasi fitur.
Module. SharedDataModule adalah ruang shared memory
yang menyimpan sampel-sampel data yang di-sense dari node sensor (accelerometer, temperatur, dan cahaya) dan data lainya yang di-share antara perceptor dengan acktuator
Service RadiogramMTS merepresentasikan layanan transport
untuk transmisi data ke remote node atau base station
Rule. TerImplication terdiri dari deskripsi Java auto-
generate untuk rule-rule perilaku agent yang didefinisikan ke dalam script file.
Rule 1 Memungkinkan timer untuk pnerimaan pesan dari
DataViewerAgent dan membuat goFalse belief message(inform, sender(dataViewer, addresses(“radiogram:’/” + DataViewerAgentNodeAddr)), ?content), !goFlase > par(timerActivationAct, adobBelief(always(goFalse)));
Rule 2 Me-state bahwa jika setelah kadaluarsa timer, operasi
pembacaan sensor diaktifasi dan juga timer di re-aktivasi timerExpired > par(timerActivatorAct, activateSensorAct);
Rule 3, 4, 5 Digunakan untuk menyimpan data sensor dan pada saat yang
sama me-disable perseptor pengindraan.
3.
temperatur(?value) > par(deactTempSensorAct, registerTempValueAct(?value));
4.
light(?value) > par(deactLightSensorAct, registerLightValueAct(?value));
5.
Acc(?accX, ?accY, ?accZ) > par(deactLightSensorAct, registerLightValueAct(?accX, ?accY, ?accZ));
Rule 6 Cek jika sample sejumlah numData telah diperoleh untuk
setiap tipe sensor dan pada kasus ini komputasi fitur dimulai. numDataSampled > computeFeatures
Rule 7 Memverifikasi bahwa fitur telah dikomputasi dengan benar.
Jika hal ini terjadi, DataMessengerAgent dinotifikasi dengan sebuah pesan.
featuresComputed(?computedFeatures) > par(resetValuesAct, inform(agentID(messenger, addresses(“radiogram://” + DataMessengerAgentNodeAddr)), value(?computedFeature)));
Rule 8 Me-state bahwa jika user menekan switch, pesan dengan fitur
yang terkomputasi terakhir yang akan dikirim ke DataViewerAgent.
switch_pressed(?computedFeatures) > inform(agentID(dataViewer, addresses(“radiogram://” + DataViewerAgentNodeAddr)), values(?computedFeatures));
Rule 9 Cek penerimaan pesan dari DataViewerAgent dan karena
goFalse, maka operasi penginderaan dihentikan. (timer di reset dan pembacaan sensor disable)
Message(inform, sender(dataViewer, addresses(“radiogram://” + DataViewerAgentNodeAddr)), ?content), goFalse > resetTimerAct, deactAccSensorAct, deactLightSensorAct, deactTempSensorAct
A special case asigning task utilities to histories is to assign 0 (false) or 1 (true) to a run
If a run is assigned 1, then the agent succeeds on that run, otherwisw it falls.
Call these predicate task spesification ψ: R
{0,1}
An
achievement task is spesified by set G of “Good” or “Goal” states : G С E The agent succeed if it is guaranteed to bring about at
least one of these state (we don’t care which one – they are considered equally good)
A maintenance goal is specified by set of B of Bad
State : : B С E
The agent successd in particular environment if it
manages to avoid all state in B – If it never performs actions which result in any state in B occuring.
Presentation 3
Min Chen, Sergio Gonzalez, and Victor C. M. Leung University of British Columbia IEEE Wireless Communication, December 2007
Paradigma client-server merupakan metode tradisional disiminasi data di WSN kemunculan event me-trigger node-node sumber di sekitarnya untuk mengumpulkan dan mengirim data ke sink sendiri-sendiri. Jumlah aliran data umumnya sama dengan jumlah node-node sumber sehingga menyebabkan konsumsi bandwidht dan energi yang cukup tinggi. Pendekatan ini menyebabkan ketidakseimbangan konsumsi energi di jaringan karena node-node yang lebih dekat dengan sink akan me-forward lebih banyak data (data dirinya maupun data yang dititipkan dari node lain)
Pada pendekatan berbasis Mobile Agent : sink node mengirimkan mobile agent ke area target untuk mengunjungi node satu per satu.; data-data sensor dikurangi dan dikumpulkan oleh agent; dan selanjutnya sesuai dengan instruksi mobile agent, data-data tersebut dikirim kembali ke sink pendekatan ini menghasilkan satu aliran lalu lintas data daripada multiple aliran lalu lintas data
Modul Cyclops Image Capturing and Interference dapat dihubungkan, melalui sebuah interface, dengan perangkat WSN seperti Crossbow’s MICA2 dan MICAZ untuk aplikasi penginderaan image. Jumlah data yang dihasilkan oleh image sensor
sangat besar. Mengirimkan gambar secara keseluruhan tidak hanya mengkonsumsi lebih banyak bandwidth dan energi, namun juga tidak efektif jika sink hanya mengevaluasi area interest tertentu saja di dalam gambar
Mobile Agent yang akan membawa kode-kode segmentasi image diberangkatkan menuju area target untuk mengunbjungi image sensor satu per satu, lalu mengumpulkan data-data image dari ROI-nya. Volume besar dari data image pada setiap sensor dikurangi ke dalam volume yang lebih kecil. Ketika keadaan lingkungan disekitar sensor berubah, mobile agent baru yang membawa algoritma segmentasi berbeda diberangkatkan kembali untuk melakukan image processing
Mother Agent yang berada di Node A, memberangkatkan agent-agent anak ke Node B dan Node C.
Ketika target bergerak dari Node B, sinyal yang diterima di Node B akan berkurang. Ketika level sinyal jatuh di bawah nilai threshold, agent anak B akan ditarik dan agent anak baru akan diberangkatkan ke D
Ketika target sudah melewati Node C, Mother Node akan jejak target sehingga Mother node melakukan migrasi ke Node C. Semua agent lama akan ditarik dan agent-agent anak baru akan diberangkatkan oleh Mother Agent baru ke Node D dan E.
Setelah target terdeteksi, mobile agent diberangkatkan untuk melakukan tracking jalur yang dilewati target. Ketika agent bermigrasi ke sensor node, agent mengumpulkan data untuk meningkatkan keakuratan pengenalan obyek.
Setelah nilai kekuratan melebihi threshold tertentu dan memenuhi kebutuhan pengenalan obyek, mobile agent menghentikan proses tracking dan mobile obyek mengembalikan hasil yang terkumpul ke sink node.
Architecture in Hierarchical Sensor Network Peran atau kapabilitas setiap node tidak sama. Sensor disegmentasi dalam bentuk cluster sehingga
metode diseminasi data terdiri dari :
▪ Intra-cluster : Setiap cluster head memberangkatkan mobile agent yang akan mengunjungi semua anggota cluster satu per satu untuk menghimpun dan melakukan aggregasi data. Setelah mobile agent kembali ke cluster head-nya, mobile agent ini akan mengirimkan data yang sudah diaggregasi ke sink node. ▪ Inter-cluster : Metode ini tidak melibatkan operasi mobile agent di dalam cluster , melainkan mobile agent bermigrasi diantara cluster head dan processing center.
Architecture in Flat Sensor Network ▪ Mobile Agent-Based Distributed Sensor Network (MADSN) merupakan paradigma berbasis agent pertama yang bisa diadopsi baik hierichical dan Flat WSN. ▪ Sink memberangkatkan beberapa mobile agent untuk secara langsung mengumpulkan data di area target. Node-node sumber diasumsikan dekat dengan sink. ▪ Metode ini menyebabkan overhead yang besar ketika mengirimkan kode-kode mobile dari sink setiap saat.
Architecture in Flat Sensor Network ▪ Pada Mobile Agent-Based WSN (MAWSN), dimungkinkan dilakukan pengurangan redudancy informasi di level :
▪ Node. Data mentah, yang dihasilkan oleh masing-masing node sensor, dikurangi oleh agent child. Lalu, hanya informasi relevan yang dikirim ke sink. ▪ Agent anak. Ketika node-node saling berdekatan, maka pengukuran nodenode tersebut akan menampilkan tingkat korelasi yang tinggi. Jadi, perlu dilakukan aggregasi data untuk mengurangi redudancy data sensor dari satu event tunggal ketika agent anak mengunjungi node-node sumber yang mendeteksi event tersebut. ▪ Mother Agent. Setelah agent-agent anak kembali ke mother agent, mother agent selanjutnya mengurangi redudancy yang terjadi di data yang terkumpul oleh berbagai agent anak.
Pada Convensional WSN data mentah yang di-sense oleh sensor-sensor ditransmisikan langsung ke sink.
Sumber : Multiple mobile agents’ itinerary planning in wireless sensor networks: survey and evaluation X. Wang, M. Chen, T. Kwon,H.C. Chao Published in IET Communications Received on 14th July 2010 doi: 10.1049/iet-com.2010.0638 In Special Issue on Distributed Intelligence and Data Fusion for Sensor Systems
Sink mengirimkan satu MA untuk berkeliling ke semua sensor secara berurutan untuk mengumpulkan informasi yang di-sense oleh sensor.
Isu-isu terkait dengan Single MA : Delay scalability. Potential Route inefficiency Trafik Load Balancing
Sumber : Multiple mobile agents’ itinerary planning in wireless sensor networks: survey and evaluation X. Wang, M. Chen, T. Kwon,H.C. Chao Published in IET Communications Received on 14th July 2010 doi: 10.1049/iet-com.2010.0638 In Special Issue on Distributed Intelligence and Data Fusion for Sensor Systems
Untuk mendisain WSN berbasis MA dengan efisiensi tinggi, terdapat 4 katageori isu : Arsitektur. Itinerary Planning. Middleware Design Hardware Design
Tujuan sistem MA multiple adalah membagi beban data fusion task ke beberapa MA.
Kinerja pendekatan ini lebih baik daripada Sistem MA tunggal jika node-node dikelompokkan dengan baik dan rute MA didisain dengan baik
Namun, Sistem MA multiple menghasilkan lebih banyak trafik daripada Sistem MA single.
Ada trade-aff antarta performance dengan efisiensi
Sumber : Multiple mobile agents’ itinerary planning in wireless sensor networks: survey and evaluation X. Wang, M. Chen, T. Kwon,H.C. Chao Published in IET Communications Received on 14th July 2010 doi: 10.1049/iet-com.2010.0638 In Special Issue on Distributed Intelligence and Data Fusion for Sensor Systems
Itinerari adalah rute yang dilalui selama migrasi mobile agent.
Itinerari planning mencakup dua isu yang harus diselesaikan oleh sink dan mobil agent secara otonom Pemilihan set node-node sumber yang akan dikunjungi oleh
mobile agent. Penentuan urutan kunjungan ke sumber-sumber dengan mempertimbangkan efisiensi energi
Kategori Itenerary Planning : Static Planning Dynamic Planning Hybrid Planning
Pada static planning, Agent itinerari ditentukan sepenuhnya oleh sink node sebelum agent diberangkatkan.
Pada static planning, Dispatcher menggunakan informasi network global terkini dan mendapatkan jalur agent efisien sebelum mobile agent dikirim.
Dua pendekatan static planning : Local closest first (LCF) Global closest first (GCF)
Asumsikan bahwa LCF dan GCF berjalan pada sensor node yang sama yang dekat denan dispatcher. LCF mencari node berikutnya dengan jarak terpendek dengan node yang saat ini berjalan, sedangkan GCF mencari nnode berikutnya yang dekat dengan dispatcher.
Algoritma genetik dapat digunakan untuk mobile agent itinerary planning dimana setiap node tidak dikunjungi berulang-ulang dalam satu putaran. Meskipun optimasi global akan diperoleh, namun penggunaan algoritma ini bukan solusi yang ringan untuk sensor node yang memiliki energi terbatas.
Dynamic planning memungkinkan mobile agent untuk menentukan node berikutnya untuk dikunjungi pada setiap titik pemberhentian di jalur migrasinya.
Rute agent dinamis harus memperhatikan trade-off antara cost migrasi dan keakuratan migrasi.
Pendekatan Dynamic planning mencari sensor node yang : Memiliki sisa energi yang terbesar Memerlukan konsumsi energi untuk migrasi agent Menyediakan informasi yang lengkap
Mobile Agent seharusnya mencoba bermigrasi ke sensor node yang meningkatkan keakuratan secara progresif sehingga jumlah node yang harus dikunjungi mobile agent dikurangi.
Pada Hybrid Planning, pemilihan set kunjungan node sumber adalah statik, sedangkan keputusan urutan kunjungan node sumber adalah dinamis.
Kosep Mobile Agent-Based Directed Diffusion (MADD) : Jika sumber di area target mendeteksi event yang
diharapkan, sumber-sumber tersebut mengirim paketpaket eksploratoty ke sink. Berdasarkan paket-paket ini sink secara statistik memilih sumber-sumber yang akan dikunjungi oleh mobile agent, lalu mobile agent secara otonom memutuskan urutan kunjungan ke sumber.
Centre location-based multiple MA itinerary planning (CL-MIP)
Chen, M., Gonzlez, S., Zhang, Y., Leung, V.C.: ‘Multi-agent itinerary planning for sensor networks’. Proc. IEEE 2009 Int. Conf. Heterogeneous Networking for Quality, Reliability, Security and Robustness (QShine 2009), Las Palmas de Gran Canaria, Spain, 2009
Direction-based Multiple MA Itinerary Planning (Agle Gap-Based MIP, AG-MIP)
Chen, M., Gonzalez, S., Leung, V.: ‘Directional source grouping for multi-agent itinerary planning in wireless sensor networks’. Proc. Int. Conf. ICT Convergence (ICTC), Jeju Isaland, Korea, 2010
Tree-based Multiple MA Itinerary Planning (Balanced Minimum Spanning Tree, BST)
Chen, M., Cai, W., Gonzalez, S., Leung, V.C.: ‘Balanced itinerary planning for multiple mobile agents in wireless sensor networks’. Proc. Second Int. Conf. Ad Hoc Networks (ADHOCNETS2010), Victoria, BC, Canada, 2010
Genetic Algorithm-based Multiple MA Itinerary Planning Cai, W., Chen, M., Hara, T., Shu, L.: ‘GA-MIP: genetic algorithm based multiple mobile agents itinerary planning in wireless sensor network’. Proc. Fifth Int. Wireless Internet Conf. (WICON), Singapore, 2010
Usulan Alternatif Teknik Metaheuristic : • Ant Colony • Simulated Aneling • Cross Entropy • Differential Evolution Min Chen, Sergio Gonzalez, and Victor C. M. Leung University of British Columbia IEEE Wireless Communication, December 2007
[1] M. Chen et al., “Mobile Agent-Based Directed Diffusion in Wireless Sensor Networks,” EURASIP J. Advances in Sig. Processing, vol. 2007. [2] Y. Tseng et al., “Location Tracking in a Wireless Sensor Network by Mobile Agents and Its Data Fusion Strategies,” Comp. J., vol. 47, no. 4, July 2004, pp. 448–60. [3] Y. Xu and H. Qi, “Mobile Agent Migration Modeling and Design for Target Tracking in Wireless Sensor Networks,” Ad Hoc Networks, vol. 6, no. 1, Jan. 2007, pp. 1–16. [4] Y. Xu and H. Qi, “Distributed Computing Paradigms for Collaborative Signal and Information Processing in Sensor Networks,” Int’l. J. Parallel and Distrib. Comp., vol. 64, no. 8, Aug. 2004, pp. 945–59. [5] H. Qi, Y. Xu, and X. Wang, “Mobile-Agent-Based Collaborative Signal and Information Processing in Sensor Networks,” Proc. IEEE, vol. 91, no. 8, Aug. 2003, pp. 1172–83. [6] M. Chen et al., “Mobile Agent Based Wireless Sensor Networks,” J. Comp., vol. 1, no. 1, Apr. 2006, pp. 14–21. [7] Q. Wu et al., “On Computing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks,” IEEETrans. Knowledge and Data Eng. , vol. 16, no. 6, June 2004, pp. 740–53.
Presentation 4
Michael Wooldridge
Hal utama yang dimiliki oleh Agent adalah OTONOM : kapabilitas melakukan aksi yang independent.
Agent adalah sistem komputer yang memiliki kapabilitas melakukan aksi yang otonom di lingkungan tertentu untuk mencapai tujuan yang didelegasikan kepadanya.
Agent melakukan close-couple atau interaksi kontinu di dalam lingkungannya : sense–decide–act–sense–decide
Thermostat Tujuan yang didelegasikan kepadanya adalah menjaga
kestabilan suhu di ruangan. Aksinya-aksinya adalah HEAT on/off
U N I X biff program Tujuan yang didelegasikan kepadanya adalah memonitor
email yang masuk dan menandainya dengan sutau flag. Aksinya-aksinya adalah GUI action .
Contoh di atas adalah contoh aplikasi trivial karena pengambilan keputusannya pun sifatnya trivial
Agent adalah sistem komputer yang mempunyai kemampuan untuk melakukan aksi otonom untuk mencapai obyektif yang diinginkan penggunanya.
Sistem Multiagent adalah sistem yang terdiri dari agent-agent yang berinteraski satu sama lain untuk melakukan kerja sama, koordinasi, dan negosiasi.
Tiga perilaku intelligent agent : Reactive, yaitu sistem memelihara interaksi yang
sedang berjalan dengan lingkungannya dan memberikan respon terhadap perubahan yang terjadi.
Pro-Active (goal directed behaviour) yang berarti
menghasilkan dan berusaha untuk mencapai goal, tidak hanya didorong oleh event, namun punya inisiatif dan mengenali opportunity
Social , yaitu kemampuan untuk berinteraksi dengan
agent-agent lainnya (dan juga mungkin manusia) melalui beberapa jenis komunikasi agent dan juga bekerja sama dengan agent-agent lainnya.
Jika lingkungan program dijamin FIX, maka program dapat mengeksekusi secara buta
Lingkungan sifatnya tidak tetap, melainkan dinamis.
Software sangat sulit membangun untuk domain dinamis : Program harus dapat menangani kemungkinan failure, lalu kemampuan untuk menentukan keputusan apakah aksi yang akan dieksekusi cukup berarti (worthed).
Sistem reaktif adalah sistem yang menjaga keberlangsungan interaksinya dengan lingkungannya dan merespon perubahan yang terjadi di lingkungan sekitarnya.
Beraksi terhadap lingkungannya sangatlah mudah (contoh ada stimulus -> response rules).
Namun, kita umumnya menginginkan agent melakukan suatu hal untuk kita. Sehingga perlu adanya goal directed behaviour .
Pro-activeness = menghasilkan dan mencoba mencapai goal, bukan dikendalikan oleh event, dan mengambil inisiatif.
Mengenali opportunity
Dunia sebenernya adalah lingkungan multi agent : Kita tidak dapat meraih goal tanpa melibatkan agent lain yang bekerja sama satu sama lainnya.
Beberapa goal dapat dicapai dengan cara interaksi dengan agent lainnya.
Kemampuan social pada agent adalah kemampuan untuk berinteraksi dengan agent lain (dapat juga manusia) melalui kerja sama, koordinasi, dan negosiasi. Istilah umumnya adalah kemampuan untuk berkomunikasi.
Kerja sama adalah bekerja secara bersamasama untuk meraih goal bersama.
Biasanya didorong oleh pernyataan bahwa “tidak ada satu agent yang bisa mencapai goalnya sendirian” atau “Kerja sama akan menghasilkan hasil yang lebih baik (misalnya, proses berjalan cepat)”
Koordinasi adalah mengelola ketergantungan antar aktifitas
Contoh, jika kita ingin menggunakan resource yang tidak di-share, maka perlu dilakukan koordinasi
Negosiasi adalah kemampuan untuk mencapai persetujuan terkait dengan kepentingan umum
Contoh dalam satu rumah, Anda menginginkan menonton film sedangkan keluarga Anda yang lain menginginkan nonton sepak bola Contoh kemungkinan deal-dealan : Anda nonton film
besok, sedangkan malam ini nonton sepak bola.
Umumnya, melibatkan offer dan counter-offer, dengan kompromi-kompromi yang dibuat oleh partisipan-partisipan.
Mobility Veracity Benevolence Rationality Learning/Adaption
Apakah Agent adalah sebatas Objek dengan nama berbeda ?
Obyek : enkapsulasi beberapa state komunikasi melalui pengiriman pesan memiliki method terkait dengan operasi yang dapat dilakukan pada state-nya
Agent otonom : memasukkan notasi otonom yang lebih kuat dari obyek. Agent
memutuskan sendiri apakah perlu atau tidak melakukan aksi yang diminta agent lainnya agent harus cerdas : punya kapabilitas fleksibel (reactive- pro active- social) agent adalah aktif : bukan provider layanan yang pasif. entitas yang perilakunya dapat diprediksi dengan mengatributkan belief, desires, dan kecerdasan rasional
Objects do it for free Agents do it because the you want to; Agents do it for money .
Apakah Agent sistem pakar dengan nama yang berbeda ?
Sistem pakar umumnya disebut “expertise about some (abstract) domain of discourse”.
Contoh : M Y C I N mengetahui penyakit-penyakit darah manusia Memiliki pengetahuan tentang penyakit-penyakit darah,
dalam bentuk RULE Dokter akan memperoleh saran ahli tentang penyakit darah dengan memberikan MYCIN fakta-fakta, menjawab pertanyaan, mengajukan query-query.
Agent ditempatkan di suatu lingkungan : MYCIN tidak peduli dengan lingkungan. Hanya
informasi yang diperoleh dengan menanyakan pertanyaan kepada penggunanya.
Agent melakukan aksi MYCIN tidak melakukan aksi kepada pasien.
Beberapa sistem-sistem pakar real-time adalah agent-agent.
Bukankah Agent adalah sebatas proyek AI ? Bukankan membangun sebuah agent terkait semua dengan AI ?
AI ditujukan untuk membangun sistem yang dapat memahami bahasa natural, mengenali, dan memahami suasana, menggunakan pengindraan umum, berfikir kreatif, dsb.
Jadi, tidakkah kita perlu menyelesaikan masalah AI untuk membangun sebuah Agent ?
Ketika membangun sebuah agent, secara sederhananya kita menginginkan sebuah sistem yang dapat memilih aksi yang tepat untuk dilakukannya, biasanya dalam domain terbatas.
Kita tidak perlu menyelesaikan semua permasalahan AI untuk membangun sebuah agent yang bermanfaat a little intelligence goes along way!
Oren Etzioni, berbicara tentang pengalaman komersil dari N E T B O T ,Inc :
W e made our agents dumber and dumber and dumber...until finally they made money .
Accessible dan inaccesible Lingkungan yang accessible adalah lingkungan di mana
di dalamnya sebuah agent dapat memperoleh informasi tentang state lingkungan secara lengkap, akurat, dan up-to-date,
Sebagian besar lingkungan komplek (Misalnya
lingkungan fisik sehari0hari atau internet) adalah lingkungan yang inaccessibe
Semakin accessible lingkungan, semakin mudah
membangun agent yang akan beroperasi di dalamnya.
Deterministic dan Non-Deterministic Lingkungan deterministic adalah lingkungan di
mana di dalamnya beberapa aksi memiliki satu akibat – Tidak ada ketidakpastian tentang state yang akan dihasilkan dari melakukan sebuah aksi.
Lingkungan nyata yang ada di dunia ini adalah
lingkungan yang non-deterministic. Lingkungan ini yang memberikan masalah besar bagi disainer agent.
Episodic dan Non-Episodic Pada lingkungan episodic, sebuah kinerja agent
bergantung pada beberapa peristiwa-peristiwa diskrit, tanpa mata rantai antar kinerja agent di skenario berbeda Lingkungan episodic lebih mudah dari sudut pandang
pengembang agent karena agent dapat memutuskan aksi apa yang harus dilakukan hanya berbasis pada episode yang saat ini sedang berjalan – Tidak perlu interaksi antara episode saat ini dengan episode yang akan datang.
Static dan Dynamic Lingkungan Static adalah lingkungan yang kondisinya tidak
berubah, kecuali jika ada aksi dari agent.
Lingkungan Dynamic adalah lingkungan yang memiliki proses
lain yang berjalan di dalamnya sehingga kondisinya berubah. Penyebab perubahan kondisi ini diluar aksi yang dilakukan agent.
Lingkungan nyata adalah lingkungan yang dinamis.
Descret dan Continue Lingkungan dinamakan diskrit jika lingkungan tersebut di
dalamnya terdapat jumlah action dan percept yang terbatas dan fix.
Ketika menjelaskan aktifitas manusia, terkadang kita menggunakan pernyataan berikut : Kemarin Jannie mengambil payung karena dia tahu (believed)
bahwa hari itu hujan dan ia ingin (wanted) tetap kering
Pernyataan di atas adalah bentuk dari folk phsycology, yaitu perilaku manusia diprediksi dan dijelaskan dengan mengatributkan sikap (attitude) seperti keyakinan (believe), keinginan (wanting), harapan (hoping), ketakutan (fearing).....
Daniel Dennett menyebutkan istilah intentional system untuk mendeskripsikan entitas-entitas yang perilakunya dapat diprediksi oleh metode pengatributan belief, desire, dan rational acumen.
Sejalan dengan sistem komputer yang semakin komplek, diperlukan abstraksi dan metafora yang lebih powerful untuk menjelaskan operasi sistem komputer – Penjelasan low level menjadi tidak praktis. Intentional stance adalah salah satu bentuk abstraksi itu.
Intentional notion adalah bentuk tool abstraksi tersebut yang memberikan kenyamanan dan cara yang familiar untuk mendeskripsikan, menjelaskan, dan memprediksi perlikau sistem komplek.
Pengembangan terpenting dalam komputasi adalah berbasis pada abtraksi baru : Abtraksi prosedural Tipe data abstrak Obyek-obyek
Agent, dan agent sebagai intentional system, merepresentasikan abstraksi powerful lebih lanjut
Asumsikan environment mungkin berada dalam set E diskrit (instantaneous state) :
Agent diasumsikan memiliki daftar action yang mungkin dilakukannya yang akan mengubah state lingkungannya
Run, r, sebuah agent di suatu lingkungan merupakan urutan perubahan environment state dan action
Run :
Environment :
Fungsi transformer state merepresentasikan perilaku lingkungan :
Catatan bahwa lingkungan : ▪ ▪
History dependent Non-deterministic
Jika , maka tidak ada state successor untuk r sehingga dikatakan bahwa run telah berakhir (Game over)
Environment selanjutnya menjadi dimana E adalah set environment state, eo є E adalah initial state, dan τ adalah fungsi transformer state
Agent adalah fungsi yang memetakan run ke action
Jadi, sebuah agent membuat keputusan tentang aksi apa yang perlu dilakukan berdasarkan histori sistem
Misalkan
adalah set dari semua agent
Sistem adalah pasangan yang terdiri dari sebuah agent dan lingkungannya
Beberapa sistem akan memiliki keterkaitan dengan kemungkinan set run. ▪ Ditulis ulang set run dari sebuah agent Ag di lingkungan Env dengan
Asumsikan
Urutan lingkungan jika : e0 adalah initial state dari Env α0 = Ag(e0 ); dan Untuk u > 0
berisi hanya run yang telah berakhir. merepresentasikan run sebuah agent di
Beberapa agent memutuskan apa yang harus dilakukanya tanpa referensi ke historinya – pengambilan keputusan oleh agent tersebut berbasiskan kondisi terkini tanpa merujuk pada semua referensi di masa lalu.
Agent tersebut dinamakan purely reactive :
Termostat adalah contoh agent reaktif :
Fungsi see adalah kemampuan agent untuk melakukan observasi lingkungannya.
Fungsi action merepresentasikan proses agent mengambil keputusan
Ouput fungsi see adalah percept
yang memetakan state lingkungan ke percept, dan fungsi action menjadi :
yang memetakan urutan perceipt ke action
Agent yang memelihara state
Agent ini memiliki struktur ata internal, di mana biasanya digunakanuntuk merekam informasi tentang state lingkunganna dan historinya.
Angap I adalah set semua state internal sebuah agent.
Fungsi tambahan next diperkenalkan, dimana memetakan state internal dan percept ke state internal :
Fungsi action sekarang didefinisikan sebagai :
di mana memetakan antara state internal ke aksi
Fungsi next diperkenalkan sebagai :
Yang memetakan state inbternal dan percept ke state internal
Agent mulai berjalan pada state internal awal i0.
Lakukan pengulangan selamanya : Agent melakukan observasi state lingkungannya,
lalu membangkitkan percept melalui see(..) Update state internal melalui fungsi next(..) Pilih aksi melalui action(..) Lakukan aksi
Agent dibangun untuk mengerjakan tugas yang didelegasikan kepadanya.
Tugas harus dispesifikasi oleh kita, namun kita menginginkan agent melakukan tugas itu tanpa kita beri tahu caranya.
Satu kemungkinan yang bisa dilakukan : mengkaitkan utilitas dengan masing-masing state – tugas agent adalah membawa state yang memaksimalkan utilitas.
Spesifikasi tugas adalah fungsi : Yang mengkaitkan bilangan real dengan setiap state lingkungan. Lalu apa manfaat dari run ? ▪ ▪ ▪ ▪
Utilityas state minimum pada run ? Utilitas state maksimum pada run ? Total utilitas state pada run ? Rata-rata ?
Kelemahan : sulit menspesifikasi long term view ketika menempatkan utilitas ke setiap individu state
Kemungkinan yang lain : menempatkan sebuah utilitas bukan ke setiap individu state, melainkan ke run itu sendiri.
Dari mana asalnya bilangan real tersebut ?
Orang-orang tidak memahami istilah utilitas – Sulit bagi orang untuk menggunakan istilah ini. Namun demikian istilah ini bekerja baik di skenario lain sebagai contoh TileWorld : Disimulasikan lingkungan grid dua dimensi di mana
terdapat agent, tile, obstacle, dan lubang. Agent dapat bergerak dalam 4 arah, ke atas, ke bawah, ke kiri, dan ke kanan. Jika agen diletakkan ke sebuah tile, maka agent dapat menekan tile Lubang harus diisi tile oleh agent dimana agent bertugas untuk mengisi sebanyak mungkin lubang yang ia mampu.
Fungsi Utilitas didefinisikan sebagai berikut :
Jadi : Jika agent mengisi semua lubang, utility = 1 Jika agent tidak mengisi satu pun lubang, utility = 0
Tulis yang menandakan probabilitas di mana run r terjadi ketika agent Ag diletakkan di lingkungan Env
Utilitas yang diharapkan (Expected Utility) agent Ag di lingkungan Env adalah :
Optimal Agent Ag di dalam sebuah lingkungan adalah agent yang memaksimalkan expected utility :
Dalam kenyataannya, optimal agent belum tentu yang terbaik. Perlu dirata-ratakan untuk menentukan apakah agent itu disebut terbaik.
Beberapa Agent tidak dapat diimplementasikan di beberapa komputer
Tulis untuk menandai bahwa agent dapat diimplementasikan di mesin (komputer) m :
Bounded optimal agent, Agbopt selanjutnya menjadi :
Kasus spesial me-assign utilitas ke histori adalah dengan me-assign 0 (false) dan 1 (true) ke sebuah run.
Jika run di-assign 1, maka agent dinyatakan sukses pada run tersebut. Begitu sebaliknya.
Inilah yang disebut sebagai Predicate Task Spesification yang ditulis dengan simbol ψ :
Lingkungan Tugas adalah pasangan (Env, ψ) dan semua lingkungan tugas.
menandakan set
Lingkungan tugas menentukan : Properti sistem di mana agent mendiami. Kriteria dimana agent akan dinilai apakah sukses atau gagal.
Catat bahwa set semua run dari sebuah agent Ag di dalam lingkungan Env yang memiliki predikat sukses ψ
Sehingga dapat dikatakan bahwa agent Ag dikatakan sukses di lingkungan (Env, ψ) jika :
Misalkan adalah probabilitas dimana run r terjadi jika agent Ag diletakkan di lingkungan Env
Sehingga probabilitas di mana ψ dipenuhi oleh Ag di Env adalah :
Dua tipe umum dari sebuah tugas adalah achievement task dan maintenance task Achievement task adalah task berbentuk “achieve state of affairs Φ” Maintenance task adalah task berbentuk berbentuk “maintain state of
affairs ψ”
Achievement task dispesifikasi oleh set G dari state “Good” atau “Goal” : G E Agent dikatakan sukses jika agen bisa mencapai setidaknya satu state
“Good”
Maintenance task dispesifikasi oleh set B dari state “Bad” : B Agent dikatakan sukses di suatu lingkungan jika agent mampu
menghindari semua state di B – Tidak pernah melakukan aksi yang menyebabkan state B
E
Agent Synthesis adalah pemrograman otomatis : Goal : sebuah program yang akan berjalan di
suatu lingkungan tugas, dan dari lingkungan tugas ini secara otomatis menghasilkan agent yang sukses di lingkungannya :
Pikirkan
seperti null di Java
Algoritma synthesis : Sound, kapan pun algoritma ini mengembalikan sebuah agent, jika agent ini sukses di lingkungan tugas yang dikirim sebagai inputnya.
Complete jika dijamin mengembalikan sebuah agent
kapan pun agent itu ada yang sukses di lingkungan tugas yang diberikan sebagai input.
Presentasi ke-5
Arsitektur Agent adalah disain piranti lunak untuk agent.
Review dokomposisi top level sbb : Perception – state – decision – action
Arsitektur agent mendefinisikan : Struktur-struktur data kunci Operasi-operasi pada struktur data Control flow antar operasi-operasi
Metodologi untuk membangun agent. Arsitektur menspesifikasi cara agent didekomposisi ke dalam konstruksi set modul-modul komponen dan cara modul-modul ini seharusnya dibuat untuk berinteraksi. Total set modul-modul dan interaksiinteraksinya harus menyediakan sebuah jawaban dari pertanyaan tentang bagaimana sebuah data sensor dan internal state saat ini dari sebuah agent menentukan aksi-aksinya dan menentukan internal state agent di waktu yang akan datang. Sebuah arsitektur mencakup teknikteknik dan algoritmaalgoritma yang mendukung metodoogi ini.
Koleksi modul-modul piranti lunak (atau piranti keras) spesifik, biasanya didisain dalam bentuk kotak-kotak dengan tanda panah yang mengindikasikan data dan control flow antar modul-modul. Deskripsi abstrak dari arsitektur adalah metodologi umum untuk mendisain dekomposisi-dekomposisi modular untuk suatu task tertentu
1956 – sekarang : Symbolic Reasoning Agent Agent menggunakan logical reasoning eksplisit
untuk menentukan apa yang harus dilakukannya
1985 – sekarang : Reactive Agent
1990 – sekrang : Hybrid Agent Arsitektur agent yang mengkombinasikan
arsitektur symbolic reasoning agent dan arsitektur reaktif
Pendekatan klasik untuk membangun agent adalah dengan memandang mereka sebagai tipe sistem berbasis pengetahuan
Pradigma ini dikenal sebagai Symbolic AI
Didefinisikan deliberative agent atau arsitektur agent : Mencakup model simbolik dunia nyata Membuat keputusan melalui symbolic reason
Transduction Problem Masalah penerjemahan dunia nyata ke dalam deskripsi
simbolik yang cukup dan akurat pada saat deskripsi ini digunakan ..... Vision, speech undertanding, learning
Representation/reasoning problem Bagaimana secara simbolik merepresentasikan informasi
tentang entitas-entitas dan proses-proses dunia nyata yang komplek, dan bagaimana membuat agent untuk menalar (reason) dengan informasi ini dalam menentukan keputusannya. .... Knowledge representation, automated reasoning, automatic planning
Sebagian besar peneliti menganggap bahwa tidak ada masalah di semua area yang diselesaikan secara sempurna.
Masalah kompleksitas algoritma manipulasi simbol : Beberapa atau bahkan hampir semua algoritma
manipulasi simbol tidak menyelesaikan masalah
Atas dasar ini, beberapa peneliti menggunakan pendekatan alternatif untk membangun agent.
Menggunakan logika untuk mengenkode teori yang mendefinisikan aksi terbaik yang dilakukan pada situasi yang diberikan.
Diberikan : ρ adalah teori tersebut (biasanya set aturan) Δ adalah database logik yang mendeskripsikan state saat ini
dari lingkungan Ac adalah aksi-aksi yang dapat dilakukan agent Δ Φ berarti bahwa Ф dibuktikan dari Δ menggunakan ρ
Goal adalah Robot membersihkan semua kotoran
Gunakan 3 predikat domain berikut : In(x,y) berarti agent berada pada (x,y) Dirt(x,y) berarti ada kotoran pada (x,y) Facing(d) berarti agent sedang menghadap ke arah d
Aksi yang mungkin : Ac = {turn, forward, suck}
Rule ρ untuk menentukan apa yang dilakukan :
Problem : Bagaimana mengkonversi input kamera ke Dirt(0,1) ? Pengambilan keputusan mengasumsikan lingkungan statik : rasionalitas kalkulatif Pengambilan keputusan melalui Theorem proving adalah komplek (mungkin bisa tdak
berkeputusan/undecidable)
Pendekatan untuk mengatasi masalah ini : Memperlemah logika Gunakan simbolik, reprresentasi non-logika Ubah titik berat penalaran dari run time ke design time.
Yoav Shoham mengenalkan pemrograman berorientasi agent pada tahun 1990 “new programming paradigm, based on a societal view of computation”.
Ide kunci : Memprogram agent dalam istilah intentional
notion seperti belief, commitment , dan intention
Setiap agent pada AGENT0 memiliki 4 komponen :
Set capability (Hal yang bisa dilakukan agent) Set belief awal Set commitment awal (hal yang akan agent lakukan) Set commitment rule
Commitment Rule Komponen kunci yang menentukan bagaimana agent
beraksi Commitment rule terdiri dari : ▪ message condition ▪ mental condition ▪ Sebuah aksi
Setiap siklus keputusan........ Kondisi message dicocokkan dengan message yangtelah diterima agent; Kondisi mental dicocokkan dengan belief-nya agent Jika aturan dieksekusi, agent menjadi commit pada action (action
ditambahkan kepada set komitmen agent)
Action dapat berupa : Private, yaitu komputasi tereksekusi secara internal. Communicative, yaitu pengiriman message
Message dibatasi dengan salah satu dari tiga tipe berikut : “request” to commit to actions “unrequest” to refrain from actions “informs” which pass on information
Jika saya menerima pesan dari Agent yang meminta (REQUEST) saya melakukan action pada waktu time, dan saya yakin (believe) bahwa : • agent tersebut saat ini adalah teman (Friend) • saya dapat melakukan action • pada waktu time, saya tidak berkomitmen (committed) melakukan action yang lain, Maka saya komitmen untuk melakukan action pada saat time.
Implementasi Agent disempurnakan oleh Thomas pada tesis doctornya di tahun 1993
Bahasa Planning Communication Agent (PLACA) dikembangkannya untuk memperbaiki kelemahan AGENT0 : yaitu ketidakmampuan agent untuk merencanakan, dan mengkomunikasikan request sebuah action
Agent di PLACA diprogram sama sebagaimana pada AGENT0 , khususnya dalam hal aturan-aturan perubahan mental
Concurrent METATEM adalah bahasa multiagent di mana di dalamnya sebuah agent diprogram dengan cara memberikannya spesifikasi logik temporal dari perilaku yang seharusnya ditunjukkannya
Spesifikasi-spesifikasi ini dieksekusi secara langsung supaya menghasilkan perilaku agent
Logika temporal adalah logika klasik yang dihasilkan dari modal operator untuk mendeskripsikan cara kebenaran dalil berubah terhadap waktu
Sebagai contoh :
berarti sekarang dan akan selalu benar bahwa agent-agent adalah penting berarti suatu waktu di masa depan ConcurrentMetaTem akan penting berarti kita bukan teman sampai kamu meminta maaf berarti besok (di state berikutnya), kamu meminta maaf
Program Metatem adalah kumpulan dari aturan :
Eksekusi berjalan oleh proses aturan-aturan pencocokan yang kontinu terhadap history, dan menjalankan aturan-aturan tersebut yang history sebelumnya memuaskan
Konsekuensi-konsekuensi di masa depan yang diinstantiasi akan menjadi commitment yang harus dipenuhi berikutnya.
Contoh Program Metatem : The Resource Controller
Aturan pertama memastikan bahwa sebuah ‘ask’ pada akhirnya diikuti dengan ‘give’ Aturan kedua memastikan bahwa hanya saty ‘give’ yang dilakukan pada satu waktu
Sistem Concurrent Metatem terdiri dari sejumlah agent (obyek), setiap obyek memiliki 3 atribut : Nama Interface Program Metatem
Agent interface memiliki dua set : Pesan yang akan agent terima (accept) Pesan yang akan agent kirim (send)
Contoh interface obyek Stack
{pop,push} = pesan diterima {pop, stackfull] = pesan dikirim
Utilities and Preferences Multiagent Encounters Dominant Strategies and Nash Equilibria Competitive and Zero-Sum Interactions The Prisoner’s Dilemma Other Symmetric 2 x 2 Interactions Dependence Relations in MAS
Misalkan terdapat dua agent (bernama agent i dan agent j). Setiap agent memiliki preference-nya masing-masing dan desire tentang apa yang seharusnya terjadi di lingkungannya.
Asumsikan set Ω = {ω1, ω2, ...} adalah hasil (outcome) atau state yang dipreferensi oleh kedua agent tersebut.
Preference agent diperoleh dengan menggunakan fungsi utilitas yang menentukan seberapa baik outcome untuk agent tersebut. ui = Ω → R dan uj = Ω → R
Utility function lead to preference ordering over outcomes. Jika ω dan ω’ adalah dua kemungkinan outcome di Ω, dan ui(ω) ≥ ui(ω’), maka outcome ω dipreferensi oleh agent i setidaknya sama dengan ω’. ω ≥i ω’ singkatan dari
ui(ω) ≥ ui(ω’)
Hal yang sama, jika ui(ω) > ui(ω’), maka outcome ω harus diprefer oleh agent i di atas ω’ ω >i ω’ singkatan dari
ui(ω) > ui(ω’)
Dengan kata lain, ω >i ω’ jika dan hanya jika ui(ω) ≥ ui(ω’) dan bukan ui(ω) = ui(ω’)
Kita dapat peroleh hubungan ≥i adalah ordering, di atas ω, yang memiliki properti sebagai berikut : Reflexivity : untuk semua ω є Ω, kita memiliki ω ≥ ω. Transivity : jika ω ≥i ω’ dan ω’ ≥i ω’’, maka ω ≥i ω’’ Comparability : untuk semua ω є Ω dan ω’ є Ω, kita memiliki ω ≥i ω’ atau ω’ ≥i ω
Fungsi utilitas adalah cara merepresentasikan preferensi agent Analoginya : Jika A memiliki $500 juta Jika B memiliki $0 Jika C memiliki $1 juta untuk didonasikan Apa yang terjadi pada utilitas A, jika A diberi uang oleh C $1 juta. Tentunya A akan memiliki tambahan uang yang tidak terlalu signifikan. Tidak banyak yang bisa dilakukan dengan $501 juta yang tidak bisa dilakukan dengan $500 juta. Apa yanbg terjadi pada utilitas B, jika B diberi uang oleh C $1 juta. Maka penambahan utilitas B akan signifikan . B akan berubah dari tidak memiliki uang sama sekali menjadi milionair.
Presentasi ke-6
Chapter 8 – 9 An Introduction to MultiAgent Systems Michael Wooldridge
We now consider agent communication languages (ACLs) — standard formats for the exchange of messages .
The best known ACL is KQML, developed by the ARPA knowledge sharing initiative. KQML is comprised of two parts: The knowledge query and manipulation language (KQML); and The knowledge interchange format(KIF).
KQML is an ‘outer’ language, that defines various acceptable ‘communicative verbs’, or performatives. Example performatives:
ask-if (‘is it true that...’) perform (‘please perform the following action...’) tell (‘it is true that...’) reply (‘the answer is...’)
KIF is a language for expressing message content .
More recently ,the Foundation for Intelligent Physical Agents (FIPA) started work on a program of agent standards—the centre piece is an Agent Comunication Laguage (ACL).
Basic structure is : performative; 20 performative in FIPA.
House keeping ; ▪ e .g.,sender etc.
content ▪ The actual content of the message ▪ Contoh :
“Inform”and“Request”are the two basic performatives in FIPA. Others are macro definitions, defined in terms of these .
The meaning of inform and request is defined in two parts : pre-condition – what must be true in order for the
speech act to succeed. “rational effect” – what the sender of the message hopes to bring about.
The content is a statement . Pre-condition is that sender : holds that the content is true; intends that the recipient believe the content; does not already believe that the recipient is a
ware of whether content is true or not.
The content is an action . Pre-condition is that sender : intends action content to be performed; believes recipient is capable of performing this
action; does not believe that sender already intends to perform action.
Why and how to agents work together?
Since agents are autonomous,they have to make decisions at run-time, and be capable of dynamic coordination
Over all they will need to be able to share: Tasks Information
If agents are designed by different individuals, they may not have common goals.
Important to make a distinction between: benevolent agents and self-interested agents
If we “own” the whole system, we can design agents to help each other when ever asked.
In this case, we can assume agents are benevolent : Our best interest is their best interest. Problem-solving in benevolent systems is cooperative
distributed problem solving (CDPS).
Benevolence simplifies the system design task enormously!
If agents represent the interests of individuals or organizations, (the more general case), then we can not make the benevolence assumption: agents will be assumed to act to further there own
interests, possibly at expense of others. potential for conflict .
May complicate the design task enormously. Strategic behavior may be required Game theory
Criteria for assessing an agent-based system.
Coherence How well the [multiagent] system behaves as a unit along
some dimension of evaluation (Bond and Gasser). We can measure coherence in terms of solution quality, how effiently resources are used, conceptual clarity and so on.
Coordination The degree to which [the agents] can avoid “extraneous”
activity [such as] synchronizing and aligning their activities (Bond and Gasser). If the system is perfectly coordinated, agents will not get in each others ’ way, in a physical or a metaphorical sense .
How does a group of agents work together to solve problems?
There are three stages: Problem decomposition Sub-problem solution Answer synthesis
The over all problem to be solved is divided into smaller sub-problems.
This is typically a recursive/hierarchical process. Sub problems get divided up also. In ACTORS, this is done until we are at the
level of individual program instructions.
Clearly there is some processing to do the division. How this is done is one design choice.
Another choice is who does the division. Is it centralized ? Which agents have knowledge of task
structure ? Who is going to solve the sub-problems?
Sub Problem Solution : The sub-problems derived in
the previous stage are solved. Agents typically share some information during this process . A given step may involve two agents synchronizing their actions .
Solution Synthesis In this stage solutions to sub-
problems are integrated again this may be hierarchical
▪ Different solutions at different levels of abstraction.
Given this model of cooperative problem solving, we have two activities that are likely to be present: Task sharing : ▪ Components of a task are distributed to component agents; ▪ How do we decide how to allocate tasks to agents ?
Result sharing : ▪ Information (partial results, etc) is distributed. ▪ How do we assemble a complete solution from the parts ?
Well known task-sharing protocol for task allocation is the contract net .
The contract net includes five stages:
Recognition; Announcement; Bidding; Awarding; Expediting.
In this stage, an agent recognises it has a problem it wants help with.
Agent has a goal, and either. . . realises it cannot achieve the goal in isolation - does
not have capability; realises it would prefer not to achieve the goal in isolation (typically because of solution quality, deadline, etc)
As a result, it needs to involve other agents.
In this stage, the agent with the task sends out an announcement of the task which includes a specification of the task to be achieved.
Specification must encode: description of task itself (maybe executable); any constraints (e.g., deadlines, quality
constraints). meta-task information (e.g., “bids must be submitted by. . . ”)
The announcement is then broadcast.
Agents that receive the announcement decide for themselves whether they wish to bid for the task.
Factors: agent must decide whether it is capable of expediting
task; agent must determine quality constraints & price information (if relevant).
If they do choose to bid, then they submit a tender.
Agent that sent task announcement must choose between bids & decide who to “award the contract” to.
The result of this process is communicated to agents that submitted a bid.
The successful contractor then expedites the task.
May involve generating further manager contractor relationships: sub-contracting. May involve another contract net.
The FIPA ACL was designed to be able to capture the contract net. cfp ( call for proposals ): ▪ Usedf or announcing a task;
propose, refuse : ▪ Used for making a proposal, or declining to make a proposal.
accept, reject : ▪ Used to indicate acceptance or rejection of a proposal.
inform, failure : ▪ Used to indicate completion of a task (with the result) or failure to do so .
How to... ... specify tasks ? ... specify qualityofser vice ? ... decide how to bid ? ... select between competing offers? ... differentiate between offers based on multiple
criteria?
In results sharing, agents provide each other with information as they work towards a solution.
It is generally accepted that results sharing improves problem solving by:
Independent pieces of a solution can be cross-checked. Combining local view scan achieve a better over all view . Shared results can improve the accuracy of results. Sharing results allows the use of parallel resources on a problem.
The first scheme for cooperative problem solving was the blackboard system.
Results shared via shared data structure (BB).
Multiple agents (KSs/KAs) can read and write to BB .
Agents write partial solutions to BB.
BB may be structured into hierarchy .
Mutual exclusion over BB required → bottleneck.
Not concurrent activity .
Compare: LINDA tuple spaces, JAVA SPACES .
Common design pattern in OO systems: subscribe/notify.
An object subscribes to another object, saying “tell me when event e happens”.
When event e happens, original object is notified.
Information pro-actively shared between objects .
Objects required to know about the interests of other objects → inform objects when relevant information arises
A group of agents may have inconsistencies in their : Beliefs Goals or intentions
Inconsistent beliefs arise because agents have different views of the world. May be due to sensor faults or noise or just because they can’t see everything.
Inconsistent goals may arise because agents are built by different people with different objectives.
Three w ays to handle inconsistency (Durf eeatal.) : Do not allow it ▪ For example, in the contract net the only view that matters is that of the manager agent. Resolve inconsistency ▪ Agents discuss the inconsistent information/goals until the inconsistency goes a way. Build systems that degrade gracefully in the face of inconsistency .
Coordination is managing dependencies between agents .
We both want to leave the room through the same door. We are walking such that we will arrive at the door at the same time. What do we do to ensure we can both get through the door ?
We both arrive at the copy room with a stack of paper to photocopy. Who gets to use the machine ?
Von Martial suggested that positive coordination is : Requested (explicit) Non-requested (implicit)
Non-requested coordination relationships can be as follow : Action equality: we both plan to do something,
and by recognizing this one of us can be saved the effort. Consequence: What I plan to do will have the sideeffect of achieving something you want to do. Favor: What I plan to do will make it easier for you to do what you want to do.
Societies are often regulated by (often unwritten) rules of behavior.
Example: A group of people is waiting at the bus stop. The bus arrives. Who gets on the bus first ?
Anothere xample: On 34th Street, which side of the side walk do you walk along ?
In an agent system, we can design the norms and program agents to follow them, or let norms evolve .
Recall how we described agents bef ore:
a function which, given a run ending in a state, gives us an action.
A constraint is then apair :
This constraint says that α can not be done in any state in E’
A social law is a set of constraints .
We can refine our view of an environment.
Focal states, F E are the states we want our agent to be able to get to .
From any focal state e є F it should be possible to get to any other focal state e’ є F (though not necessarily right away).
A useful social law is then one that does not prevent agents from getting from one focal state to another .
We can also design systems in which social laws emerge .
T-shirt game (Shoham and Tennenholtz): Agents have both a red t-shirt and a blue t-shirt and wear
one. Goal is for every one to end up with the same color on. In each round, each agent meets one other agent, and decides whether or not to change their shirt. During the round they only see the shirt their pair is wearing — they don’t get any other information.
What strategy update function should they use ?
Simple majority : Agents pick the shirt they have seen the most.
Simple majority with types : Agents come in two types. When they meet an agent
of the same type, agents pass their memories. Other wise they act as simple majority .
Highest cumulative reward : Agents can “see” how often other agents (some
subset of all the agents) have matched their pair .They pick the shirt with the largest number of matches .
Just as we have individual intentions, we can have joint intentions for a team of agents .
Levesque defined the idea of a joint persistent goal (JPG)
A group of agents have a collective commitment to bring about some goal Φ, “move the couch”.
Also have motivation µ,“Simon wants the couch moved”
The mental states of agents mirror those in BDI agents.
Agents don’t believe that is satsified Φ, but believe it is possible.
Agents maintain the goal until a termination condition is reached.
The terminations condition is that it is mutually believed that : goal is satisfied; or goal is impossible; or the motivation is no longer present.
You and I have a mutual belief that p if I believe p and you believe p and I believe that you believe p and I believe that you believe that I believe p and....
The termination condition is achieved when an agent realises that, the goal is satisfied, impossible and so on.
But it doesn’t drop the goal right away.
Instead it adopts a new goal — to make this new knowledge mutually believed.
This ensures that the agents are coordinated.
They don’t stop working towards the goal until they are all appraised of the situation.
Mutual belief is achieved by communication.
Another approach to coordinate is to explicitly plan what all the agents do .
For example,come up with a large STRIPS plan for all the agents in a system.
Could have:
Centralized planning for distributed plans One agent comes up with a plan for every body Distributed planning. A group of agents come up with a centralized plan for another group of agents. Distributed planning for distributed plans. Agents build up plans for them selves, but take into account the actions of others .
Different agents plan to achieve their goals using these operators and then do:
Interaction analysis :do different plans affect one another? Saf ety analysis : which interactions are problematic? Interaction resolution : treat the problematic interactions as critcal sections and enforce mutual e xclusion.