Tag: algorithm

NEO Blockchain Concepts: Delegated Byzantine Fault Tolerance

In my last post, we had a look at NEO-CLI. Today, we will have a look at the basic concept of consensus NEO implements inside. There are a lot of ways to implement consensus in any blockchain platform you see around. All of them tends to solve the historical problem named “The Byzantine Generals’ Problem”. If you want to read the original paper on the problem, here it is.

 

The generals and their problems

The simplest way one could possibly describe this problem would be to describe it as the problem of determining the true outcome of a vote. One might wonder how that can be a problem since counting the votes and tallying them up should easily tell the result. Let’s imagine a scenario where we have 5 generals. They want to attack a city in the middle but all of them are in different geographic location. In a simplistic picture, the setup would look something like:

Byzantine Generals

They need to attack or retreat in sync or according to a predetermined plan. To act in unison, they proposed a way to vote for the next move. They decided to vote daily and the majority vote wins. Since they are not in the same geographic place, they use couriers to convey their vote amongst each other.

One doesn’t need to think for long to land on the conclusion that this whole plan has some inherent flaws. First, the couriers are humans and not that reliable, they can get captured, bribed to work for the enemy. They can get killed, lose the message or deliver the wrong message. Secondly, the generals themselves can be bribed in the same way to betray each other. And last but not the least, any general can make an inappropriate decision due to stupidity and failure to assess the situation or both.

Distributed computing by default inherits this problem since it works with a similar setup. Actors in the system can fall into the same trap as these generals. They can malfunction or act in an untrustworthy way to threaten or destabilize the system.

 

Delegated Byzantine Fault Tolerance

As it was mentioned before that there are numerous ways to solve this problem. Bitcoin paved a way of solving this problem through its Proof Of Work mechanism. Hyperledger Fabric improved upon the same principles through Practical Byzantine Fault Tolerance mechanism. NEO, on the other hand, proposes Delegated Byzantine Fault Tolerance.

Let’s assume we are living in Zion and there is a leader, preferably NEO. In this case, NEO is a delegate of Zion. In this world, he just can’t assume this role by his heroics, he has to gain votes from the citizen of Zion. All citizen votes for delegates like NEO and there are multiple delegates. The delegates are responsible for making the laws of Zion.

In any moment of time, if the citizen of Zion is not satisfied with a delegates proposal of laws, they can vote for a different delegate next time. Delegates are constantly notified of the demands of the citizen. They document it on a ledger, and yes you thought it right, this ledger is the analogy of our blockchain. These demands are added one after another and laws are passed focused towards keeping the citizens of Zion happy.

 

Zion-Delegates

 

But a single delegate can’t pass a law anytime he wishes to. The laws are passed in a periodic manner. When it is time to pass a law, a random delegate is chosen, let’s call him the speaker. The speaker proposes the law based on the demands of the citizens. The job of the speaker is to show how the proposed law increases the happiness index of Zion. And then he shares the law he is proposing to the other delegates. The delegates then have the job to decide whether the speaker’s calculations were correct and the laws are aligned to the common goal. They also verify the newly improved happiness index calculation. If 66% of the delegates believe that the calculation is correct and it is an improvement, the law gets finalized and passed.

What if the new law has failed to get 66% of delegates approval? Then the whole process starts over and a new speaker is selected.

How this is translated in NEO blockchain

This whole concept is reflected in NEO blockchain. Anyone who owns NEO is a stakeholder, thus a citizen. They want to create transactions, transfer, exchange assets. They do not participate in the bookkeeping of the blockchain. To do that one node needs to be a delegate as in NEO blockchain world, a bookkeeping node. There are certain criteria to be fulfilled to be a bookkeeping node in NEO blockchain. This includes dedicated internet connections and a certain amount of GAS. The demands are analogous to transactions. When they are put together by a bookkeeping node, a new block is created, which is analogous to a law. The happiness number is the hash of the aforementioned block.

Common Pitfalls: The dishonest speaker

What if the speaker is dishonest? What if he sends wrong versions of the law to some of the delegates?

Evil Speaker

In this scene, the evil speaker sends different versions of the law to different delegates. So, when the delegates communicate with each other they send different versions of the law. In this case, the leftmost delegate will get the accurate version of the law and will be able to calculate the happiness index properly. The rest of the delegates will fail to do so, failing the consensus.

Common Pitfalls: The dishonest delegate

The dishonest delegate scenario should be self-explanatory now.

Evil Delegate

In this scenario, we have an honest speaker who sends the same version of the law to every delegate but the rightmost delegate is dishonest. He sends a different version B to everyone else. In this case, 2 of the delegates will be able to calculate the happiness index properly. But the will only be able to verify it from the speaker’s version. It will reach 66% consensus and the law will be passed. But the result of this session will deem the rightmost delegate to be faulty. This data can be used for the next time of citizen vote where they chose their delegates.

By the definition here the minimum threshold for faulty delegates in the system is f=(n-1)/3 where n is the number of active delegate nodes.

To read more about this whole process, please go through the official NEO doc.

Hope this helps clear up how NEO views consensus. Next, we will see how this can be demonstrated between NEO-CLI nodes.

 

 

 

Posted on by Swagata Prateek Featured 0

Neo Blockchain On Azure: Introduction to NEO-CLI

In my previous post, we started with a small NEO private net. Today, we will take a quick look into NEO-CLI and what it offers. Although it is named NEO-CLI, in practicality, this is a full blown NEO blockchain node instead of just a CLI tool to communicate with it. NEO offers two node types – GUI and CLI. I think the suffix comes from that and I wanted to explicitly mention it since it is a tad confusing.

At first, we will try to connect to our newly created private net. To do that, we will start with installing a separate installation of NEO-CLI. Installing NEO-CLI is pretty straight forward. You will need .Net core installed in your machine. If you don’t follow the instruction here.

Installation

I’m currently using an Ubuntu 16.04 as a reference OS. After installing .Net core framework you will need to install the NEO-CLI package. And since Im on a debian it was quite easy to do so the following way:

sudo apt-get install libleveldb-dev sqlite3 libsqlite3-dev

Configuration

We are testing and my local machine doesn’t have a frame of reference of the test private net we just created over Azure. To give this node a frame of reference we need to configure its SeedList to point to our own private net. What is a seed list? Simply put, it is nothing more than a list of URLs as described in the official NEO documentation.  This is the first set of nodes NEO-CLI will try to connect to when it boots up.

To configure the aforementioned SeedList, we will modify the protocol.json file, under the neo-cli directory.

We need to update the SeedList section of the configuration the following way:

“SeedList”: [
     "IP_or_FQDN_of_Azure_Private_Net_Host:20333”
 ],

If you opt to use the public test net, rename the protocol.testnet.json to protocol.json and you should be good to go.

Booting up the node

Now, it is time to start the node, we are going to invoke:

dotnet neo-cli.dll --log --nopeers

The log option will log the smart contract information and nopeers makes the node only connect to the seed nodes from the configuration file. this is something we want since this is a private network.

Creating a new wallet

Let’s create a new wallet then.

neo> create wallet mywallet.db3

NEO-CLI will ask for password twice for the wallet, pick your desired password. And copy the address and pubkey to keep it a safe place. If you forget the public key you can use list key command to see it.

More on protocol.json

Before we end this one, we will have one last look at the protocol.json configuration file for our node.

{
  "ProtocolConfiguration": {
    "Magic": 56753,
    "AddressVersion": 23,
    "StandbyValidators": [
        "02b3622bf4017bdfe317c58aed5f4c753f206b7db896046fa7d774bbc4bf7f8dc2",
        "02103a7f7dd016558597f7960d27c516a4394fd968b9e65155eb4b013e4040406e",
        "03d90c07df63e690ce77912e10ab51acc944b66860237b608c4f8f8309e71ee699",
        "02a7bc55fe8684e0119768d104ba30795bdcc86619e864add26156723ed185cd62"
    ],
    "SeedList": [
        "127.0.0.1:20333",
        "127.0.0.1:20334",
        "127.0.0.1:20335",
        "127.0.0.1:20336"
    ],
    "RPCList":[
      "http://127.0.0.1:30333"
    ],
    "SystemFee": {
        "EnrollmentTransaction": 1000,
        "IssueTransaction": 500,
        "PublishTransaction": 500,
        "RegisterTransaction": 10000
    }
  },

  "ApplicationConfiguration": {
    "DataDirectoryPath": "Chains/privnet",
    "NotificationDataPath": "Chains/privnet_notif",
    "RPCPort": 20332,
    "NodePort": 20333,
    "WsPort": 20334,
    "UriPrefix": [ "http://*:20332" ],
    "SslCert": "",
    "SslCertPassword": "",
    "BootstrapFile":"",
    "NotificationBootstrapFile":"",
    "DebugStorage":1
  }
}
  • The Magic field contains a uint value that denotes the source network of the message.
  • The StandbyValidators field are the validating nodes in the private node. It is the list of public keys of aforementioned validating nodes. We created 4 wallet here in this specific example and thus we have 4 entries here. 4 is the minimum number of nodes here to be listed for reaching a consensus.
  • SeedList is configured to localhost in this example configuration since NEO-CLI is booting up against the localhost node.
  • SystemFee section is the section that defines the system fee. As the configuration states, the registration fee for assets is 100000 GAS depicted by the RegisterTransaction field. EnrollmentTransaction field defines the registration fee for book-keepers. IssueTransaction is the fee for distributing assets. Finally the PublishTransaction is the fee for smart contracts.

 

That sums it up for this time. Next, we are going to have a look at how consensus works in NEO. And finally we will write a smart contract on NEO in C#. 🙂

Posted on by Swagata Prateek Featured 1

গ্রাফ সার্চ – এ* সার্চ

গ্রাফ সার্চ নিয়ে কচকচানো শুরু করার কারণ আমি বেশ কয়েকদিন আগে একটি অ্যাপ এর কাজে এটি ব্যবহার করেছিলাম। ভাবলাম লিখে ফেলা উচিত, তাই শুরু করলাম। লেখাটা পড়ার আগে আপনার যা যা জানা থাকলে ভালো তা হচ্ছে।

  1. বেসিক গ্রাফ (http://en.wikipedia.org/wiki/Graph_%28mathematics%29)
  2. গ্রাফ ট্রাভের্সাল (http://en.wikipedia.org/wiki/Graph_traversal)

গ্রাফ সার্চের অসংখ্য মেথডের মধ্যে এ* সার্চ বেশ পরিচিত হবার কারণ এটি অনেক জায়গায় বিশাল কানেক্টেড একটি গ্রাফ এর এক প্রান্ত থেকে অন্য প্রান্তে যাবার রাস্তা খুঁজে বের করার জন্যে ব্যবহৃত হয়। যেসব জায়গায় এটি সবচেয়ে বেশি ব্যবহৃত হয় তা হচ্ছে:

  1. রুবিক কিউব সলভ করার জন্যে
  2. ম্যাপ এ রাউট সার্চ করার জন্যে
  3. রোবট নেভিগেশন রাউট বের করার জন্যে
  4. কোন গেইম এ পাথ, রাউট সার্চ করার জন্যে

অন্য সব অ্যালগরিদম থেকে এটির ব্যবহার এতো বেশি হবার কারণ এটি শুরু এবং শেষের নোড খোঁজার জন্যে শুরু এবং শেষের নোড এর আশেপাশের নোড গুলো থেকে শুরু করে। অন্য একটি কারণ হচ্ছে এ* সার্চ শুধুমাত্র একটি নোড হতে অন্য নোডের দূরত্ব (cost) ছাড়াও একটি অনুমেয় দূরত্ব(Heuristic cost) ব্যবহার করে।

যদি এখনো পর্যন্ত যা বলছি তা কঠিন লাগে তাহলে আসুন একটি বাস্তব উদাহরণ এ চলে যাই।

আমরা প্রথমে শুরু করছি একটি গ্রাফ দিয়ে। ধরে নেই আমাদের গ্রাফটি দেখতে এরকম:

Graph1

সহজ বাংলায় এখানে একটি ছোট গ্রাফ আছে যার নোডসংখ্যা ৫ টি এবং কোন নোড থেকে অন্যান্য নোড এ যাবার cost নোড গুলোর edge এ লেখা। যেমন S থেকে A  যাবার জন্যে Cost 1. A থেকে G তে যাবার Cost হচ্ছে ১২. অন্যান্য সকল গ্রাফ সার্চিং অ্যালগরিদম এর মতো শুধুমাত্র path cost এর উপর এটি নির্ভর করেনা। আপনার ঠিক এর পর যেটি দরকার হবে সেটি হচ্ছে একটি Heuristic Cost . এখন প্রশ্ন আসতেই পারে কিভাবে Heuristic Cost আমরা ঠিক করবো। এই ক্ষেত্রে আমরা আমাদের এক নোড থেকে অন্য নোডের Expected Cost বসিয়ে নিয়েছি। তবে আপনি চাইলে এই Heuristic Cost ও নির্ণয় করার পদ্ধতিগুলো পরীক্ষা করতে পারেন। আমরা সেগুলো পরবর্তী কোন টিউটোরিয়াল এ দেখবো।

আসুন ধরে নেই আমাদের Heuristic Cost Table এরকম:

Graph2

আমাদের শুরু করবার নোড হবে S এবং শেষ করবার নোড হবে G। আসুন দেখি এ* সার্চ কিভাবে সঠিক পথ টি খুঁজে বের করে। আমরা একটি priority queue ব্যবহার করবো এ ক্ষেত্রে। আপনি যদি Priority Queue কি না জেনে থাকেন, অনুগ্রহ করে জেনে নিন এখান থেকে।

মনে করি লিস্টটির নাম Closed List, এটির ব্যবহার ব্যাখ্যা করার থেকে দেখে নেয়াটাই বুদ্ধিমানের কাজ হবে। অাপাতত জেনে রাখুন এটি একটি লিস্ট। আমাদের শুরু করার নোড হচ্ছে S , আমরা যেতে চাই G তে। আসুন দেখি, আমরা কিভাবে সেটি করতে পারি। প্রথমে নেই S কে। S এর সাথে Attached Node হচ্ছে A এবং B। তাহলে S থেকে G তে যেতে হলে আগে আমাকে A অথবা B তে যেতে হবে। তার মানে হচ্ছে যে নোড টি থেকে আপনি শুরু করবেন তার সাথে সংযুক্ত সকল নোড কে আপনার আগে বিবেচনায় আনতে হবে অথবা node টি expand করতে হবে।

সবার শুরুতে S এর Total Cost হিসেব করি:

c(s) = g(s) + h(s)

এখানে g(s) হচ্ছে S এ আসার Cost. S এ আসতে আমার তেমন কোন খরচ হয়নি বিধায় আমি এটিকে ধরে নিচ্ছি শূন্য। এবং h(s) হচ্ছে S এর heuristic cost যেটা আমরা table থেকে দেখে পাচ্ছি 7. এখন আমাদের কাজ হচ্ছে S এর সাথে সংযুক্ত সকল নোড বিবেচনায় আনা, মানে S expand করা। S কে expand করলে আমরা পাই A এবং B ।

c(s) = 0 + 7

মনে করি শুরুতে আমরা A তে যাবো।

এখন S হতে A তে যাবার Cost নির্ণয় করার উপায় হচ্ছে S থেকে A তে যাবার Cost এবং A এর Heuristic Cost যোগ করা। মনে করি:

c(S-A) = ( g(s)+g(a) ) + h(a)

এখানে c(S-A) হচ্ছে S হতে A তে যাবার Total Cost. g(s) হচ্ছে s এ আসার Cost. এখানে যেটি শুন্য। কারণ, s থেকে আমরা শুরু করছি। A তে যাবার Cost হচ্ছে 1. A এর Heuristic Cost হচ্ছে 6. তাহলে সম্পূর্ণ Cost দাঁড়ায়:

c(S-A) = ( 0+ 1 ) + 6 =7

অনুরূপ ভাবে S হতে B যাবার পর Cost দাঁড়ায়

c(S-B) = ( 0+ 4 ) + 4 =8

কারণ, s এ আসতে 0 এবং B আসতে 4 এবং B এর heuristic cost হলো 4 . এখন আমাদের অবস্থা নিচের মতো:
(sav)Graph

খেয়াল করলে দেখবেন, এখানে closed_list নামে একটি queue আছে। আমরা যখনি কোন নোড পুরোপুরি expand করে ফেলবো তখনি সেটিকে এখানে নিয়ে নেবো, যাতে পরে এটিকে Expand না করা লাগে। তাই আমরা এখানে S এর সব attached node (A, B) ভিসিট করে ফেলেছি বলে S কে closed_list এ রেখে দিয়েছি। আর ডান পাশে যে Tree টি তৈরী হচ্ছে তাকে বলবো আমরা Search Tree.

এখন যেহেতু A এবং B ভিসিট করা শেষ, আমাদের পরবর্তী টার্গেট A অথবা B expand করা। A এবং B এর মধ্যে কোনটি আগে করবো? যার Total cost কম তারটি আগে। এখানে A এর Total Cost 7 যেখানে B তে আসার Total Cost হচ্ছে 8, তাই এটি আগে expand করবো। A হতে শুধু B,C,G তে যাওয়া যায়। তাই ৩ টি পথের ই Total Cost বের করতে হবে। তাই Total Cost হবে:

c(S-A-B) = ( g(s)+g(b)+g(c) ) + h(c)

c(S-A-B) = ( 0+1+2) +4 = 7

অনুরূপভাবে,

c(S-A-C) = (0+1+5) + 2 = 8

c(S-A-G) = (0+1+12) + 0 = 13

(sav)Graph3যেহেতু A নোডটি আমাদের expand করা শেষ সেহেতু আমি A কে closed_list এ পাঠিয়ৈ দিবো। এখন সার্চ ট্রি এর দিকে লক্ষ্য করুন। প্রশ্ন হচ্ছে কোনটি আপনি expand করবেন? ট্রি এর সকল Leaf Node গুলো খেয়াল করুন (যেগুলো এখনো expand হয়নি)। নোডগুলো হচ্ছে:

  1. s-a-b
  2. s-a-c
  3. s-a-g
  4. s-b

এখন এর মধ্যে সবচেয়ে কম Total Cost হচ্ছে s-a-b এর। এটি এখন expand করতে হবে।

s-a-b এর শেষ নোড b, তাহলে b expand করি। b থেকে শুধু c তে যাওয়া যায় ।

c(s-a-b-c) = (g(s) + g(a) + g(b) + g(c)) + h(c)

c(s-a-b-c) = (0+1+2+2) + 2 = 7

যেহেতু B নোডটি আমাদের expand করা শেষ সেহেতু আমি B কে closed_list এ পাঠিয়ৈ দিবো।

(sav)Graph4

এখন আমাদের Leaf Node (ট্রি এর তলার নোড গুলো যেগুলো এক্সপান্ড করা হয়নি) সেগুলো হচ্ছে

  1. s-a-b-c
  2. s-a-g
  3. s-a-c
  4. s-b

যেহেতু s-a-b-c এর Total Cost কম সেহেতু আমরা এটিই expand করবো, মানে এটির শেষ নোড c expand করবো। c থেকে শুধু g তে যাওয়া যায়। তাহলে s-a-b-c-g এর total cost হচ্ছে

c(s-a-b-c-g) = (g(s) + g(a) + g(b) + g(c) + g(g) ) + h(g)

c(s-a-b-c-g) = (0+1+2+2+3) + 0 = 8

আমরা C কেও closed_list এ ঢুকিয়ে দেবো কারণ, এটি expanded হয়ে গেছে।

(sav)Graph5

এখন খেয়াল করলে দেখবেন আমাদের expand করার মতো path এবং তাদের Total Cost হচ্ছে:

  1. s-a-b-c-g = 8
  2. s-a-c = 8
  3. s-a-g = 13
  4. s-b = 8

এখানে s-a-b-c-g এবং s-a-c এবং s-b এর Total cost এক ই। এখন কোনটি expand করবো?

এখন আমাদের সমস্যা সমাধান করার জন্যে খেয়াল করে দেখুন alphabetically dictionary sort এ s-a-b-c-g আগে আসে, এরপর আসে s-a-c এবং তার পরে s-b

তাহলে s-a-b-c-g expand করা উচিত। কিন্তু এটি g তে চলে এসেছে এবং এখানেই আমরা আসতে চেয়েছিলাম। তাই, এই s-a-b-c-g ই আমাদের খুঁজতে থাকা পথ।তার মানে হচ্ছে আপনার এ* সার্চ এ যদি এক্সপান্ড করতে যে নোডটি সিলেক্ট হবে সেটিই যদি গোল নোড হয়, আপনি আপনার পথ পেয়ে গেছেন।

এটি ই সবচেয়ে ভালো পথ কিনা সেটি নিয়ে কথা বলবো পরের টিউটোরিয়াল এ। সাথে থাকবে একটি স্যাম্পল উইন্ডোজ ফোন অ্যাপ।

হ্যাপী কোডিং!

Posted on by Swagata Prateek 7

Bus Map Dhaka – What can be next and how it can be done

Usually I talk about pretty current stuffs, let’s talk future now. And the future is needed to be talked now. Because after some days in this young app industry simple rss readers won’t be considered a quality app anymore. If you look around, Windows Phone in Bangladesh has walked a pretty silent but significant path. And I’m quiet happy that I walked a little too.

I hope the one who is reading this do know Bus Map Dhaka for Windows Phone. If you dont know, the following is the link: http://www.windowsphone.com/en-bd/store/app/bus-map-dhaka/3795f088-028a-4958-bea6-a2d0eb243bd

Now, let’s start talking how this was made. When I started doing this, the first thing that came into my mind is the actual scenario of Dhaka, if you really expect a local bus to come in the very right time exactly every day,  I guess you have optimism as your profession. So, along with finding the best route and other basic operations, I had to believe someday I would face the challenge which will “actually” solve the problem.

Traffic jams are usually one of the common phenomena here, very common as in like brushing your teeth everyday. If it’s not there, you get surprised. But it’s not the only thing that can keep you getting on the right bus. There’s bad road situations, there’s bus shortage, possibly anything that you can’t predict or manage.

I thought big big plans, like putting devices on buses and tracking down each one of them. But think once, just once. When nobody is even curious about putting proper fitness checks on a bus, maintaining  a device would be a overkill for them, and of course will lead my dream service to perish.

What I had it mind was a pretty simple one. If you ever heard of Ant Colony Optimization, I believe in case of Dhaka, it would come to a greater use . Because the shortest path is not always the “right path”.

If you want to know about ant colony optimization algorithm do a wiki read here:
http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Ant_Colony_System

I wanted to follow the traditional Ant Colony Optimization trait here. Let’s put a small city like Dhaka with us like below:

1

Pretty simple for Dhaka, eh? 😀 Let’s keep it simple for understanding. You will see Node D is kind of the hub of the city, much like our motijheel, mohakhali or other big bus junctions, right? Now, in this city there can be a number of buses, right? Essentially a Bus Route is nothing but a number of these nodes ordered by bus stops.

Let’s make some bus routes, shall we?
1. A-C-E

2. C-D-E-B-A

3. D-E-C-A

For simplicity lets assume all these bus goes and comes back in the same order. Now, I know what you guys are thinking, if I put “distance metrics” on these paths, it’s easy to find a suitable bus route. Like, if you want to take A trip from A to D you can chose bus number 2 or 3. Question is which one should you pick? What if there is more traffic jam in B-E junction and less in C-E? These data changes over time, even in fraction of ten minutes.  You can’t possibly decide every time.

Here ant colony comes so handy. The very basics of Ant Colony Optimization is based on how ants find best paths. In the natural world, ants  wander randomly and after finding food return to their colony while they continuously lay down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food. So, the fact is who knows the best path right now, the bus that just has gone to that path a few minutes ago. Just like the ant. The only deficit we have here is pheromone trail left by ants. Now, remember what we have in hand. We cant put too much on a local bus as they wont take care of it properly.

But what about known bus counters? If we manage to find only time-stamps of a bus arriving at a bus-stoppage somehow, we don’t need to know which one came, just spotting one on a counter, much like spotting an ant on a node.   And based on the frequency of that timestamp, you can actually verify the frequency of buses coming down there. If the adjacent roads are not doing well with traffic jams, you are bound to have a lesser frequency and if it’s smooth sailing you will have a solid frequency. Even if that sounds awkward we can even track ticket sales, although that would be far off, still a usable heuristic metric to understand whether people are actually getting up on a bus or not.

Now, based on that. We want to go to D from A.

We have two bus routes, 2 and 3. Now which to pick? All we have to do is check the pheromone/our very own heuristic cost metric trails and the route that currently has a more favorable reinforcement/feedback. No matter what comes in the road, traffic jams or stuff, within minutes, these would be updated. And as the buses are continuously traveling, the metric will always be updated. And further more, you can even predict a possible next bus time from this too. Or predict a best possible route to go from one place to another on a car. I know, for Dhaka, it might be a bit long shot, still…worth a try.

So, if you believe every bus is a ant running on a direction (although these are defined rather than random). Actually that makes us one step closer to goal. Because logically ant colony optimization finds a best path. As our possible paths are already defined, we don’t have to go through the first state.

There should be usually two steps of ant colony optimization:
1. Edge selection
2. Pheromone Update

As our paths are already defined, edge selection is basically finding eligible bus routes to go from one place to another, it could be a multiple bus journey but I will write about that later.

procedure BMD_Heuristic
    while(not_termination)
       TraverseRoutes()
       RouteActions()
       UpdateMetrics()
    end while
  end procedure

Let me know what you guys think of it and how can you help NerdCats take it to the next level. See ya!

Posted on by Swagata Prateek 3